题目：
1222. 密码脱落 - AcWing题库文章来源：https://www.toymoban.com/news/detail-808659.html
文章来源地址https://www.toymoban.com/news/detail-808659.html
思路：
代码：
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1010;
int f[N][N];//表示以L和R为两端点的字符串的“最长”回文序列长度
char s[N];//存储输入的字符串
int main()
{
scanf("%s",&s);
int n=strlen(s);
//递归枚举字符串的长度
for(int len=1;len<=n;len++)
{
//枚举字符串左端点
for(int L=0;L+len-1<n;L++)
{
int R=L+len-1;
if(len==1)f[L][R]=1;
else
{
//按照字符串f的最长回文串是否包含左右端点s[L]和s[R]划分（注：回文串可不连续）
if(s[L]==s[R])f[L][R]=f[L+1][R-1]+2;//回文串一定包含左右端点
if(f[L+1][R]>f[L][R])f[L][R]=f[L+1][R];//回文串含右不含左
if(f[L][R-1]>f[L][R])f[L][R]=f[L][R-1];//回文串含左不含右
if(f[L+1][R-1]>f[L][R])f[L][R]=f[L+1][R-1];//回文串左右均不含
}
}
}
printf("%d",n-f[0][n-1]);
return 0;
}到了这里，关于1222. 密码脱落（dp划分）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
