POJ-1159-Palindrome

最少のアルファベットを挿入して文字列にします.
元の文字列と逆さまの文字列を最長の共通文字列にすればOKです.
メモリが大きすぎるという問題も考えられますが、5000*5000を2*5000の配列に変えて解決しました.
操作のたびに配列が1つ上に移動する限り、常に2つの階層の1次元配列のみが使用されます.
これは,その層を使用した配列が使用されず,後の操作に影響を及ぼさないことに基づいている.

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
    int dp[5][5001];
    char str[5001],str1[5001];
    int n;
    while(scanf("%d%s",&n,str+1)!=EOF)
    {
        for(int i=n,j=1;i>=1;i--)
           str1[j++]=str[i];
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                int x1=i;
                x1=1;
                if(str[i]==str1[j])
                {
                    dp[x1][j]=dp[x1-1][j-1]+1;
                }
                else
                    dp[x1][j]=max(dp[x1-1][j],dp[x1][j-1]);
            }
            for(int j=1;j<=n;j++){
                dp[0][j]=dp[1][j];
                dp[1][j]=dp[2][j];}
        }
        printf("%d
",n-dp[0][n]);
    }
    return 0;
}