Palindrome

5
Ab3bd

2
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
char str[5010];
char s[5010];
int dp[2][5010];  //dp[5010][5010], 
int main()
{
	int n;
    while(~scanf("%d",&n))
    { 
        int i,j;
        scanf("%s",str);
        for(i=0;i<n;i++)
        {
        	//scanf("%c",&str[i]);//Output Limit Exceeded
        	s[n-1-i]=str[i];
        }
	    memset(dp, 0, sizeof(dp));
	//dp的无后效性，可以优化内存，运用滚动数组 
        for(i = 1; i <= n; i ++)
		{
            for(j = 1; j <= n; j++)
			{
                if(str[i-1] == s[j-1]) dp[i%2][j] = dp[(i-1)%2][j-1] + 1;//dp[i][j]=dp[i-1][j-i]+1; 
                else dp[i%2][j] = max(dp[(i-1)%2][j], dp[i%2][j-1]);  // dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
        printf("%d\n", n-dp[n%2][n]);  //n-dp[n][n] 
    }
	return 0;
} 
<span style="font-family: Arial; font-size: 14.44444465637207px; line-height: 25.98958396911621px;">滚动数组实际是一种节省空间的办法，时间上没啥优势，多用于DP中，举个例子吧： </span><p style="margin-top: 0px; margin-bottom: 0px; padding-top: 0px; padding-bottom: 0px; font-family: Arial; font-size: 14.44444465637207px; line-height: 25.98958396911621px;"></p><p style="margin-top: 0px; margin-bottom: 0px; padding-top: 0px; padding-bottom: 0px; font-family: Arial; font-size: 14.44444465637207px; line-height: 25.98958396911621px;"></p><p style="margin-top: 0px; margin-bottom: 0px; padding-top: 0px; padding-bottom: 0px; font-family: Arial; font-size: 14.44444465637207px; line-height: 25.98958396911621px;">一个DP，平常如果需要1000×1000的空间，其实根据DP的<strong>无后效性</strong>，可以开成2×1000，然后通过滚动，获得和1000×1000一样的效果。滚动数组常用于DP之中，在DP过程中，我们在由一个状态转向另一个状态时，很可能之前存储的某些状态信息就已经无用了，例如在01背包问题中，从理解角度讲我们应开DP[i][j]的二维数组，第一维我们存处理到第几个物品，也就是阶段了，第二维存储容量，但是我们获得DP[i],只需使用DP[i - 1]的信息，DP[i - k],k>1都成了无用空间，因此我们可以将数组开成一维就行，迭代更新数组中内容，滚动数组也是这个原理，目的也一样，不过这时候的问题常常是不可能缩成一维的了，比如一个DP[i][j]需要由DP[i - 1 ][k],DP[i - 2][k]决定，i<n，0<k<=10;n <= 100000000;显然缩不成一维,正常我们应该开一个DP[100000005][11]的数组，结果很明显，超内存，其实我们只要开DP[3][11]就够了DP[i%3][j]由DP[(i - 1)%3][k]和DP[(i - 2)%3][k]决定，空间复杂度差别巨大。</p><p style="margin-top: 0px; margin-bottom: 0px; padding-top: 0px; padding-bottom: 0px; font-family: Arial; font-size: 14.44444465637207px; line-height: 25.98958396911621px;"><span style="background-color: rgb(245, 245, 245); color: rgb(51, 51, 51); font-family: Helvetica, Tahoma, Arial, sans-serif; line-height: 24px;"><strong>无后效性</strong>，就是说当前状态是历史的完全总结，和如何达到这一个状态无关。</span></p>

例如，对于这道单词接龙的题目，每个单词最多用两次。
那么“当前接到的单词”就不能概括整个“历史”，因为同样是接到的这个单词，以前考虑过的单词究竟是用过
没有，用过多少次，将同样影响今后的发展，而单一的状态参量无法概括这些信息。如果把这些信息加到状态
参量中，状态太多（指数级），动态规划也没有多大意义。

如果影响历史的信息并不多，我们可以通过升维的方法让我们的状态具有无后效性，
所以我们在思考状态的时候，指导思想就是“简洁而又完全的概括历史”