问题：
求给定输入字符串的最长回文子序列（子序列不要求连续）。
用LPS(i,j)表示从字符串第i个字符到第j个字符的最长回文子序列的长度，字符串的长度为n，则要求LPS(1,n),则：
LPS(i,j)=0; i>j;
LPS(i,j)=1; i==j;
LPS(i,j)=LPS(i+1,j-1)+2; str[i]==str[j];
LPS(i,j)=max(LPS(i+1,j),LPS(i,j-1)); str[i]!=str[j];
// zuichanghuiwen2.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
#include<string>
using namespace std;
int c[20][20];
void LPS(string str)
{
int m = str.length();
int j;
for (int j = 0; j < m; j++)
for (int i = j + 1; i < m; i++)
c[i][j] = 0;
for (int i = 0; i < m; i++)
c[i][i] = 1;
for(int l=2;l<=m;l++) //这里一定要按长度从短开始算
for (int i = 0; i<m-l+1; i++)
{
j = i + l - 1;
if (str[i] == str[j])
c[i][j] = c[i + 1][j - 1] + 2;
else
c[i][j] = c[i + 1][j] > c[i][j - 1] ? c[i + 1][j] : c[i][j - 1];
}
}
void rebuild(string str)
{
int m = c[0][str.length() - 1];
int mi;
for (auto i = 0; i < str.length(); i++)
if (str[i] == str[i + m - 1]) {
mi = i;
break;
}
for (int i = mi; i < mi + m; i++)
cout << str[i];
}
int main()
{
string str("dgdfgdfabcacbagfgfg");
LPS(str);
rebuild(str);
while (1);
return 0;
}
原文：http://www.cnblogs.com/linear/p/6641890.html