[Acwing蓝桥杯DP] 1222. 密码脱落

题目链接：1222. 密码脱落 - AcWing题库

题目大意：有一个字符串s，加入n个字符，使其变成一个回文串，求n的最小值

从当前样子变成初始状态需要添加叶子的数量 等价于 当前样子变成最大的回文串需要剪去的叶子的数量
即至少脱落多少个种子 等价于 总数量 - 最大回文子序列的长度

数据范围:  字符串的长度小于等于1000

分析：

这个是区间DP

区间DP应当先枚举区间长度。

闫氏DP分析法：

集合：f [ i ][ j ] 表示：区间 i ~ j的回文子序列的集合；

属性：长度最大值

区间划分：（1）不取 i ，不取 j  // f [ i + 1][ j - 1]

                  （2）取 i ，不取 j  // f [ i ][ j -1] 

                  （3）不取 i，取 j  // f [ i -1][ j ]

                  （4）取 i ，取 j // f[ i ][ j ] + 2 当且仅当 s [ i ] = s [ j ]

观察发现 第（2）种和第（3）种均包含第（1）种

所以要覆盖所有的情况 只需要考虑（2）（3) （4）这三种情况即可 不漏

求最大值时候，可以覆盖 ；求方案数时候不能覆盖。但都需要不漏情况，考虑完全

状态转移：f [ i ][ j ] = max( f [ i - 1][ j ] , f [ i ][ j - 1 ] );

             当s [ i ] = s [ j ]时候 f [ i ][ j ] = max ( f [ i ][ j ] , f [ i - 1][ j - 1] +2 ); 

初始化：当长度为1时候 i = j ，一个字符本身必定是一个回文串

代码：

#include 
using namespace std;
const int N=1010;
char s[N];
int f[N][N];
int main()
{
    scanf("%s",s);
    int n=strlen(s);
    for(int len=1;len<=n;len++)
    {
        for(int i=0;i+len-1)
        {
            int j=i+len-1;
            if(len==1)f[i][j]=1;//初始化
            else
            {
                f[i][j]=max(f[i+1][j],f[i][j-1]);
                if(s[i]==s[j])
                {
                    f[i][j]=max(f[i][j],f[i+1][j-1]+2);
                }
            }
        }
    }
    cout<0][n-1]<<endl;//f[0][n-1]表示最长回文串长度
    return 0;
}

END!!!