题意：求LPS (Longest Palidromic Subsequence) 最长回文子序列。和回文串不同，子序列是可以不连续的。
分析：1. 推荐->还有一种写法是用了LCS的思想，dp[i][j]表示i到j的最长回文串长度，状态转移方程：
1. dp[j][j+i-1] = dp[j+1][j+i-2] + 2; (str[j] == str[j+i-1])
2. dp[j][j+i-1] = max (dp[j+1][j+i-1], dp[j][j+i-2]); (str[j] != str[j+i-1])
2. 转化为LCS问题，将字符串逆序，然后和本串求LCS就是LPS的长度，但是前一半是LPS的一半，可以补全
代码1：
/************************************************
* Author :Running_Time
* Created Time :2015-8-7 14:26:22
* File Name :UVA_11404.cpp
************************************************/
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int MAXN = 1e3 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
string ans[MAXN][MAXN];
int dp[MAXN][MAXN];
char str[MAXN];
void LPS(void) {
int len = strlen (str + 1);
memset (dp, 0, sizeof (dp));
for (int i=1; i<=len; ++i) dp[i][i] = 1;
for (int i=1; i<=len; ++i) ans[i][i] = str[i];
for (int i=2; i<=len; ++i) { //区间长度
for (int j=1; j+i-1<=len; ++j) { //[j, j+i-1]
if (str[j] == str[j+i-1]) {
if (i == 2) {
dp[j][j+i-1] = 2;
ans[j][j+i-1] = ans[j][j] + ans[j+i-1][j+i-1]; continue;
}
dp[j][j+i-1] = dp[j+1][j+i-2] + 2;
ans[j][j+i-1] = str[j] + ans[j+1][j+i-2] + str[j+i-1];
}
else if (dp[j+1][j+i-1] > dp[j][j+i-2]) {
dp[j][j+i-1] = dp[j+1][j+i-1];
ans[j][j+i-1] = ans[j+1][j+i-1];
}
else if (dp[j][j+i-2] > dp[j+1][j+i-1]) {
dp[j][j+i-1] = dp[j][j+i-2];
ans[j][j+i-1] = ans[j][j+i-2];
}
else {
dp[j][j+i-1] = dp[j+1][j+i-1];
ans[j][j+i-1] = min (ans[j+1][j+i-1], ans[j][j+i-2]);
}
}
}
int mlen = dp[1][len];
for (int i=0; i<mlen; ++i) {
printf ("%c", ans[1][len][i]);
}
puts ("");
}
int main(void) { //UVA 11404 Palindromic Subsequence
while (scanf ("%s", str + 1) == 1) {
LPS ();
}
return 0;
}
代码2：
/************************************************
* Author :Running_Time
* Created Time :2015-8-7 14:26:22
* File Name :UVA_11404.cpp
************************************************/
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int MAXN = 1e3 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
struct Ans {
int len;
string s;
}dp[MAXN][MAXN];
char str[MAXN], rstr[MAXN];
int main(void) {
while (scanf ("%s", str + 1) == 1) {
int len = strlen (str + 1);
for (int i=1; i<=len; ++i) {
rstr[len-i+1] = str[i];
}
for (int i=0; i<=len; ++i) {
dp[0][i].len = 0, dp[0][i].s = "";
}
for (int i=1; i<=len; ++i) {
for (int j=1; j<=len; ++j) {
if (str[i] == rstr[j]) {
dp[i][j].len = dp[i-1][j-1].len + 1;
dp[i][j].s = dp[i-1][j-1].s + str[i];
}
else if (dp[i][j-1].len > dp[i-1][j].len) {
dp[i][j].len = dp[i][j-1].len;
dp[i][j].s = dp[i][j-1].s;
}
else if (dp[i-1][j].len > dp[i][j-1].len) {
dp[i][j].len = dp[i-1][j].len;
dp[i][j].s = dp[i-1][j].s;
}
else {
dp[i][j].len = dp[i-1][j].len;
dp[i][j].s = min (dp[i-1][j].s, dp[i][j-1].s);
}
}
}
int mlen = dp[len][len].len;
string ans = dp[len][len].s;
for (int i=0; i<mlen/2; ++i) printf ("%c", ans[i]);
int j;
if (mlen & 1) j = mlen / 2;
else j = mlen / 2 - 1;
for (; j>=0; --j) printf ("%c", ans[j]);
puts ("");
}
return 0;
}