求最长回文子序列

状态划分:

集合:

所有S[L~R]之间的回文子序列的集合,那么本题就是求f[0][n-1]

属性:

长度的最大值

可重但不漏的按L,R是否在子序列里面分成:

1. L,R都在,但可能不存在 f[L+1][R-1]+2
2. L在 f[L][R-1]+1(无法直接状态对应,那么利用覆盖直接取L~R+1之间最大即可)
3. R在 f[L+1][R]+1(跟第二种同理)
4. L,R都不在 f[L+1][R-1]

注意:不能按i,j线性dp,需要用到区间dp,先循环长度,再循环左端(同时算出右端点即可)

#include<cstdio>
#include<cstring>
#define 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 l = 0;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;
                if(f[l][r-1] > f[l][r]) f[l][r] = f[l][r-1];
                if(f[l+1][r] > f[l][r]) f[l][r] = f[l+1][r];
            }
        }
    printf("%d\n",n-f[0][n-1]);

    return 0;
}