题意：一个长为N的字符串( 3 <= N <= 5000)。问最少插入多少个字符使其变成回文串。
题目链接：http://poj.org/problem?id=1159
——>>状态：dp[i][j]表示第i个字符到第j个字符组成的字符串变成回文串的最少插入次数。
状态转移方程：
若sz[i] == sz[j]。则：dp[i][j] = dp[i + 1][j - 1];
否则：dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
提交，5000 * 5000的int ——> 5000 * 5000 * 4 bytes 约（/ (2 ^ 20)）等于5 * 5 * 4 MB = 100 MB > 65536 K = 64 M，会MLE的。
。
假设开成short。约 50M < 64M。能够了喔。不错！
更好的办法，用滚动数组的思想优化。。
#include <cstdio>
#include <algorithm> using std::min; const int MAXN = 5000 + 1; char sz[MAXN];
int dp[2][MAXN]; void Dp(int N)
{
int nState = 0;
for (int i = N - 1; i >= 0; --i)
{
dp[1 ^ nState][i] = 0;
for (int j = i + 1; j < N; ++j)
{
if (sz[i] == sz[j])
{
dp[1 ^ nState][j] = dp[nState][j - 1];
}
else
{
dp[1 ^ nState][j] = min(dp[nState][j], dp[1 ^ nState][j - 1]) + 1;
}
}
nState ^= 1;
} printf("%d\n", dp[nState][N - 1]);
} int main()
{
int N; while (scanf("%d", &N) == 1)
{
scanf("%s", sz);
Dp(N);
} return 0;
}
开short来AC的写法：
#include <cstdio>
#include <algorithm> using std::min; const int MAXN = 5000 + 1; char sz[MAXN];
short dp[MAXN][MAXN]; void Dp(int N)
{
for (int i = 0; i < N; ++i)
{
dp[i][i] = 0;
if (i + 1 < N)
{
if (sz[i] == sz[i + 1])
{
dp[i][i + 1] = 0;
}
else
{
dp[i][i + 1] = 1;
}
}
}
for (int nLen = 3; nLen <= N; ++nLen)
{
for (int i = 0; i < N; ++i)
{
int j = i + nLen - 1;
if (j >= N) break;
if (sz[i] == sz[j])
{
dp[i][j] = dp[i + 1][j - 1];
}
else
{
dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
}
}
}
} void Output(int N)
{
printf("%d\n", dp[0][N - 1]);
} int main()
{
int N; while (scanf("%d", &N) == 1)
{
scanf("%s", sz);
Dp(N);
Output(N);
} return 0;
}