POJ1159---Palindrome（dp，LCS）
题意理解：
给定一个字符串，问给这个字符串添加多少字符可以使得其为字符串。emmm，其实是个最长公共子序列问题，原序列长度-原序列和逆序列的最长公共子序列就是所求的答案（也就是添加的都是不在最长公共子序列的字符，去平衡一下）
最长公共子序列：
最长公共子序列（LCS）
dp[i][j]：字符串s1…si和字符串t1…tj对应的LCS长度。
递推关系：
dp[i][j]=dp[i-1][j-1]+1; （s[i-1]=t[i-1]）//字符串从0开始存放。
dp[i][j]=max(dp[i-1][j],dp[i][j-1]); （其他）
边界控制：
dp[i][j]=0(i=0||j=0) //意味着至少有一个字符串为空。
滚动数组优化下空间即可~
AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;int dp[2][5005];
char a[5005], b[5005];int main()
{int i, j, N;while (cin >> N) {cin >> a;for (int i = 0; i < N; i++)b[i] = a[N - i-1];memset(dp, 0, sizeof(dp));for (int i = 1; i <= N; i++)for (int j = 1; j <= N; j++){if (a[i - 1] == b[j - 1])//数组从0开始。dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + 1;elsedp[i % 2][j] = max(dp[(i - 1) % 2][j], dp[i % 2][j - 1]);}cout << N - dp[N % 2][N] << endl;}system("pause");
}