本文主要是介绍poj-1159-Palindrome-学习滚动数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给你一串字符串，让你求最少加入几个字符，才能使得这个字符串是个回文串。
做法：
设a[i]是这个字符串,b[i]是这个字符串的逆序串。
那么a[i],b[i]的最长公共子序列就是所求的字符串里拥有的最大的回文串。
然后用总串长减去最大的回文串长度即为所求。
求最长公共子序列的公式为：
dp[i][j]=max(dp[i-1] [j],dp[i][j-1])
if(a[i]==b[i])
dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
如果直接求的话，势必要开一个5001*5001的数组，铁定MLE。
有一下两种解决方法：
1，开short int型数组
这是poj返回的结果：
2，运用动态数组。
根据dp滚动的过程我们可以知道，dp【i】【j】的值不会与dp[i-2][0.....n]的值有关系。
那么可以把dp[i][j]的值覆盖到dp[i-2][j]上。即dp[i][j]为dp[i%2][j]；
poj返回的结果：
对比以上两种方法，显而易见的可以得出2的方法很节约空间，就是耗时略长。
1，short int数组
#include<iostream>
#include<stdio.h>
#include<string.h>
#define max(a,b) (a>b?a:b)
using namespace std;
short int dp[5001][5001];
int main()
{int a[5001];int b[5001];int i,j;int n;char str;cin>>n;getchar();for(i=1;i<=n;i++){scanf("%c",&str);a[i]=str;b[n-i+1]=str;}for(i=0;i<=n;i++){dp[i][0]=0;dp[0][i]=0;}for(i=1;i<=n;i++){for(j=1;j<=n;j++){dp[i][j]=max(dp[i][j-1],dp[i-1][j]);if(a[i]==b[j]){dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);}}}int len;len=dp[n][n];printf("%d\n",n-len);return 0;
}2，滚动数组
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int main()
{int a[5001];int b[5001];int dp[10][5001];int i,j;int n;char str;cin>>n;getchar();for(i=1;i<=n;i++){scanf("%c",&str);a[i]=str;b[n-i+1]=str;}dp[1][0]=dp[0][0]=0;for(i=0;i<=n;i++){dp[0][i]=0;}for(i=1;i<=n;i++){for(j=1;j<=n;j++){dp[i%2][j]=max(dp[i%2][j-1],dp[(i-1)%2][j]);if(a[i]==b[j]){dp[i%2][j]=max(dp[i%2][j],dp[(i-1)%2][j-1]+1);}}}int len;len=dp[n%2][n];printf("%d\n",n-len);return 0;
}这篇关于poj-1159-Palindrome-学习滚动数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
