POJ 1159 Palindrome(区间动归 滚动数组)

题目链接POJ 1159

题目大意

给定长为n (n≤5000) 的字符串，让你求至少添加多少个字符能够使它变成回文串。

分析

很明显的一道区间动规题，一开始的思路是用dp[i][j]表示从下标i到下标j变成回文串所需的最小字符： 状态的转移就是：

{if(s[i]==s[j]),else,dp[i][j]=dp[i+1][j−1]dp[i][j]=min(dp[i+1][j],dp[i][j−1])+1 一开始用递归写，MLE，改成递推后险过，应该是数据太弱。5000*5000都没爆。。。 后面看见可以用 滚动数组优化，大大节约了空间。 由于我这种做法中一个状态是由前两阶（阶表示的是串的长度）的状态决定的，所以前两阶的状态也要保存下来需要开3排数组dp[3][MAXN]

别人博客中的写法是先把整个反转过来，就变成了一个类似于求最长公共子序列的问题了，这样就只用2排数组了。

代码

动规的代码看着就是舒服哈哈

#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #include<cstdlib> #include<queue> using namespace std; const int INF=999999999; const int MAXN=5005; int n; int dp[3][MAXN]; string s; void Work() { for(int i=0;i<s.size();i++)dp[0][i]=0; for(int i=0;i<s.size()-1;i++) dp[1][i]= (s[i]==s[i+1]) ? 0 : 1; int k=1; for(int len=3;len<=s.size();len++) { k=(k+1)%3; for(int i=0;i<=s.size()-len;i++) { if(s[i]==s[i+len-1]) dp[k][i]=dp[(k+1)%3][i+1]; else dp[k][i]=min(dp[(k+2)%3][i],dp[(k+2)%3][i+1])+1; } } cout<<dp[(s.size()-1)%3][0]<<endl; } int main() { while(scanf("%d",&n)!=EOF) { cin>>s; Work(); } }