密码脱落(用最长公共子序列的区间划分)

#include <iostream>
#include <cstring>
using namespace std;
char s[1010];
char re[1010];
int dp[1010][1010];
int main(){
    cin>>s;
    int n=strlen(s);//算出输入字符的长度
    for(int i=0;i<n;i++){
        re[i+1]=s[n-1-i];//创造逆序数组，从下标为1开始
    }
    for(int i=n;i>0;i--){
        s[i]=s[i-1];//把正序的数组也搬迁到从下标为1开始
    }
    for(int i=1;i<n+1;i++){
        for(int j=1;j<n+1;j++){
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                if(s[i]==re[j])dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
        }
    }//统计正序和逆序中最长的公共子序列
    cout<<n-dp[n][n];//字符串的长度减去最长的公共子序列即可得到掉落的数量
}