区间dp

密码脱落

题目连接： https://www.acwing.com/problem/content/1224/

 

 

思路：

 首先因为是dp题，需要集合划分， 因为是求最大值，所以可以有重复但是不能遗漏，

集合划分的依据：[l,r] 之间回文子序列的集合

 

 

区间dp 的遍历方法一般是先遍历区间长度在遍历左端点，长度为len，左端点是l，则右端点l+len-1

 

 

 

code:

#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N =1100; int f[N][N]; char s[N]; int n; int main() { scanf("%s",s+1); n = strlen(s+1); for(int len=1; len <= n; len ++ ) for(int l = 1; l+len-1<=n ; l++ ){ int r=l+len -1 ; if(len == 1) f[l][r]=1; else{ if(s[l]==s[r]) f[l][r] = f[l+1][r-1]+2;//这里注意一下len可以等于2 f[l][r] = max(f[l][r],f[l][r-1]); f[l][r] = max(f[l][r],f[l+1][r]); } } printf("%d\n",n-f[1][n]); return 0; }