题意：一个长为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;
}#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;
}