1、问题描述

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

2、分析

需要理解的几个概念：

---回文

---子序列

---子串

这一篇文章描述了利用动态规划求解两个序列的最长公共子序列（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 <
     
       arr[i][j-1]?arr[i-1][j]:arr[i][j-1]);37                 }38             }39         }40         //cout << arr[length1][length2]<
      
       =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             }else53             {54                 if(arr[i][j -1] >= arr[i - 1][j])j--;55                 else56                     i--;57 58             }59 60         }61         return print;62 63     }64 65 };