poj1159(类LCS的转移方程)

/*
translation:
给出一串字符串，求最少插入几个字符才能形成回文串。

solution:
基本dp,LCS类转移方程
思路很简单，将原字符串及其反串求LCS，将原本字符串长度减去LCS长度就是答案。
状态定义和转移方程都和LCS一样。

note:
该题目需要用滚动数组，不然会MLE。所以相应的求解方式也作出改变。详见代码。
理解滚动数组求解方式：只要画出网格图来代表原来的dp[i][j]，就可以发现所求
的dp值只和前一行和当前行有关系。所以用dp[i][0]表示当前行，dp[i][1]表示
前一行。

date:
2016.8.20
*/
#include <iostream>
#include <cstdio>

using namespace std;
const int maxn = 5000;

char str[maxn], restr[maxn];
int n, dp[maxn][2];//dp[i][0]代表当前的状态，dp[i][1]代表过去的状态

int main()
{
//freopen("in.txt", "r", stdin);
    while(~scanf("%d", &n)) {
scanf("%s", str);
for(int i = 0; i < n; i++)restr[i] = str[n-i-1];
//printf("%s\n%s\n", str, restr);

for(int i = 0; i <= n; i++){
dp[i][0] = dp[i][1] = 0;
}//初始化状态边界

for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(str[i-1] == restr[j-1])dp[j][0] = dp[j-1][1] + 1;
elsedp[j][0] = max(dp[j-1][0], dp[j][1]);
}
for(int j = 1; j <= n; j++)dp[j][1] = dp[j][0];
}
//printf("%d\n", dp[n][1]);
printf("%d\n", n - dp[n][0]);
    }
    return 0;
}

其实可以用动态滚动数组来代替普通的滚动数组，代码如下：

#include <iostream>  
#include <cstdio>

using namespace std;
const int maxn = 5000;

char str[maxn], restr[maxn];
int n, dp[maxn][2];

int main()
{
//freopen("in.txt", "r", stdin);
    while(~scanf("%d", &n)) {
scanf("%s", str);
for(int i = 0; i < n; i++)restr[i] = str[n-i-1];
//printf("%s\n%s\n", str, restr);

for(int i = 0; i <= n; i++){
dp[i][0] = dp[i][1] = 0;
}//初始化状态边界

int k;
for(int i = 1; i <= n; i++) {
k = i & 1;    
for(int j = 1; j <= n; j++) {
if(str[i-1] == restr[j-1])dp[j][k] = dp[j-1][k^1] + 1;
elsedp[j][k] = max(dp[j-1][k], dp[j][k^1]);
}
//for(int j = 1; j <= n; j++)dp[j][1] = dp[j][0];
//动态滚动数组版本节省了上面注释掉的循环赋值过程，从1000多ms降到了900多ms
}
//printf("%d\n", dp[n][1]);
printf("%d\n", n - dp[n][k]);
    }
    return 0;
}