构造回文【简单DP= =】

构造回文

时间限制：1秒

空间限制：32768K

给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？
输出需要删除的字符个数。

输入描述:

输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.

输出描述:

对于每组数据，输出一个整数，代表最少需要删除的字符个数。

输入例子1:

abcda
google

输出例子1:

2
2

题意：给定一个串，求最长回文子序列

思路： 等价求s串和s反转串的最长公共子序列。。。好**啊wocao

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;

const int N=1000+5;
char s[N];
char s1[N];
ll dp[N][N];

int main(void){

    while(scanf("%s",s+1)==1){
        int n=(int)strlen(s+1);
        for(int i=n,j=1;i>=1;i--,j++){
            s1[j]=s[i];
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(s[i]==s1[j]) dp[i][j]=dp[i-1][j-1]+1;
                else{
                    dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }

        printf("%lld\n",1ll*n-dp[n][n]);
    }


    return 0;
}