51nod 1092【区间dp】

思路：

简单的区间dp,从小区间到大区间，随便写。

还有一种是那啥，n-LCS。。。具体不说了，赶时间）））= =、

#include <stdio.h>

#include <string.h>

#include <iostream>

using namespace std;

typedef long long LL;

const int N=1e3+10;

char s[N];

int dp[N][N];

int main()

{

    int n;

    scanf("%s",s+1);

    n=strlen(s+1);

    memset(dp,0,sizeof(dp));

    for(int len=1;len<n;len++)

        for(int j=1;j<=n;j++)

        {

            if(s[j]==s[j+len])

                dp[j][j+len]=dp[j+1][j+len-1];

            else

                dp[j][j+len]=min(dp[j+1][j+len],dp[j][j+len-1])+1;

        }

    printf("%d\n",dp[1][n]);

    return 0;

}