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 };

?

轉載于:https://www.cnblogs.com/LCCRNblog/p/4444058.html

總結

以上是生活随笔為你收集整理的动态规划求一个序列的最长回文子序列（Longest Palindromic Substring ）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。