蓝桥杯2016年第七届真题-密码脱落

解题思路:将此字符串倒过来，找它与原串的最长公共子序列，最后用原串的长度减去最长公共子序列的长度即可。

参考代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+10;
int dp[N][N];
char c[N];
char b[N];
int main()
{
    int i,j;
    cin >> c;
    int len=strlen(c);
    int k=len-1;
    /*for(i=0;i<len;i++){
		b[i]=c[len-i-1];
	}*/
	for(i=0;i<len;i++){
		b[i]=c[k--];
	}
    for(i=1;i<=len;i++){
    	for(j=1;j<=len;j++){
    		
			if(c[i-1]==b[j-1]){
				dp[i][j]=dp[i-1][j-1]+1;
			}else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
		}
    }
	cout<<len-dp[len][len]<<endl;
	
	return 0;	
}