poj 1159

不得不说本人愚盹，动态规划的题也做了不少，但就是不得要领。

此题 实质上是求最长公共子串，最长公共字串的dp解法想了半天想不出来，只能看百度百科了http://baike.baidu.com/view/2020307.htm。

题目描述：http://poj.org/problem?id=1159

求完公共子串长度，然后用总长度一减即是结果

没用滚动数组，short 水过

代码：

#include <stdio.h>
#include <stdlib.h>
short maxS(short a,short b)
{
    return a>b?a:b;
}
short dp[5002][5002];
char a[5002];
int main(int argc, char** argv) {

    short n,i,j,len;
    
   scanf("%d",&n);
    
        getchar();
        for(i=1;i<=n;++i)
        {
            scanf("%c",&a[i]);
        }
        //getchar();
        memset(dp,0,sizeof(dp));
        for(i=0;i<=n;++i)
        {
            dp[i][0]=0;
            dp[0][i]=0;
        }
        for(i=1;i<=n;++i)
        {
            for(j=n;j>=1;--j)
            {

                if(a[i]==a[j])
                {
                    dp[i][n-j+1]=dp[i-1][n-j]+1;
                }
                else
                {
                    dp[i][n-j+1]=maxS(dp[i][n-j],dp[i-1][n-j+1]);
                }
            }
        }
        printf("%d\n",n-dp[n][n]);
    
    return (EXIT_SUCCESS);
}