C++ 最长上升公共子序列

解题思路:正常模拟有点难以判断，但是这是一个经典的回文串，将字符串与自己的翻转串求最长公共子序列长度 ，字符串的长度减去最长子序列的长度 就是答案

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

string s;

char s1[1010],s2[1010];

int dp[1010][1010];//i到j的最长公共子序列长度

int main()

{

    cin>>s;

    int n=s.size();

    for(int i=1;i<=n;i++) s1[i]=s[i-1];

    for(int i=n;i>=1;i--) s2[i]=s1[n-i+1];

    //找出最长公共子序列长度 n-最长就是答案

    //套一下LCS的模板

    for(int i=1;i<=n;i++){

        for(int j=1;j<=n;j++){

            if(s1[i]==s2[j]){

                dp[i][j]=dp[i-1][j-1]+1;

            }else{

                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

            }

        }

    }

    int ans=n-dp[n][n];

    cout<<ans<<endl;

    return 0;

}