最长回文子序列

题目描述

所谓回文串就是正读和反读都一样的字符串。给定一个字符串，通过删除若干字符，都可以变成回文词。请计算最少删除多少字符才能够让给定的字符串变成回文。

提示：区间 dp

#include<cstring>
#include<iostream>
using namespace std;
int f[2005][2005];
char s[2005];
int main(){
    memset(f,0x3f,sizeof f);
    cin>>s+1;
    int len=strlen(s+1);
    for(int i=1;s[i];i++)f[i][i]=0;
    for(int l=2;l<=len;l++){
        for(int i=1;i+l-1<=len;i++){
            int j=i+l-1;
            if(s[i]==s[j]){
                if(l==2)f[i][j]=0;
                else f[i][j]=f[i+1][j-1];
            }else f[i][j]=min(f[i][j-1],f[i+1][j])+1;
        }
    }
    cout<<f[1][len];
    return 0;
}