动态规划求一个序列的最长回文子序列（Longest Palindromic Substring ）

1、问题描述

给定一个字符串（序列），求该序列的最长的回文子序列。

2、分析

需要理解的几个概念：

---回文

---子序列

---子串

http://www.cnblogs.com/LCCRNblog/p/4321398.html这一篇文章描述了利用动态规划求解两个序列的最长公共子序列（Longest Common Sequence）。

假设LCS（X,Y）表示序列X，Y的最长公共子序列，LPS（X）表示X的最长回文子序列；

在设序列X1为X的装置序列（逆序），比如X=“123”，X1=“321”；

则有：

LCS（X,X1） = LPS（X）。

 1 class Solution {
 2 public:
 3     string longestPalindrome(string s) {
 4         string s1(s.rbegin(),s.rend());
 5         //s1.reserve()
 6         //cout << s1 <<endl;
 7 
 8         return LCS(s,s1);
 9 
10     }
11 
12 
13     string LCS(string str1,string str2)
14     {
15 
16         int length1,length2;
17         //int** arr;
18         const int row=110;
19         const int col=110;
20         int arr[row][col];
21 
22         length1 = str1.length(); 
23         length2 = str2.length();
24         
25         memset(arr,0,sizeof(arr));
26         for (int i=1;i<=length1;i++)
27         {
28             for (int j=1;j<=length2;j++)
29             {
30                 if (str1[i-1] == str2[j-1])//这里为什么要用i-1，j-1，因为str中的下标从0开始
31                 {
32                     arr[i][j]=arr[i-1][j-1]+1;
33                 }
34                 else
35                 {
36                     arr[i][j]=(arr[i-1][j] > arr[i][j-1]?arr[i-1][j]:arr[i][j-1]);
37                 }
38             }
39         }
40         //cout << arr[length1][length2]<<endl;
41 
42         //打印其中一个最长子序列
43         string print="";
44         for (int i=length1,j=length2;i>=1&&j>=1;)//这里是倒序打印的
45         {
46             if (str1[i-1] == str2[j-1])
47             {
48                 //cout << str1[i-1]<<" ";//按照这样会倒序打印
49                 print = str1[i-1]+print;
50                 i--;
51                 j--;
52             }else
53             {
54                 if(arr[i][j -1] >= arr[i - 1][j])j--;
55                 else
56                     i--;
57 
58             }
59 
60         }
61         return print;
62 
63     }
64 
65 };