给定一个字符串，问最少添加多少个字符可以使得这个字符串变成回文串
if(str[i]==str[j]) dp[i][j] = dp[i+1][j-1]
else dp[i][j] = min(dp[i][j-1],dp[i+1][j]);
可以看出，dp[i][j] 要么是从dp[i+1][] 这个状态转移而来，要么是从dp[i][j-1]这个状态转移而来（这个只要从小到大枚举j即可）
所以我们可以用滚动数组来压缩空间
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <math.h>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#include <algorithm>
#include <iostream>
#include <string>
#include <functional>
#include <unordered_map>
typedef __int64 LL;
const int INF = ; /* if(str[i]==str[j])
dp[i][j] = dp[i+1][j-1]
else
dp[i][j] = min(dp[i][j-1],dp[i+1][j])
*/
const int N = + ;
int dp[][N];
char str[N]; int main()
{
int n;
while (scanf("%d%s", &n, str+) != EOF)
{
memset(dp, , sizeof(dp));
for (int i = n; i >= ;--i)
{
for (int j = i + ;j <= n;++j)
{
if (str[i] == str[j])
dp[i%][j] = dp[(i + )%][j - ];
else
dp[i%][j] = std::min(dp[(i + )%][j], dp[i%][j - ])+;
}
}
printf("%d\n", dp[][n]);
}
return ;
}