演算法導論學習之最長迴文子序列

演算法導論學習之最長迴文子序列

本問題是《演算法導論》第15章的思考題15-2（Longest Palindromic Subsequence)。

最長迴文子序列LPS問題描述如下：一個字元串有許多子序列，可以通過刪除某些字元而變成迴文字元串，字元串「cabbeaf」，刪掉『c』、e、『f』後剩下的子串「abba」就是迴文字元串，也是其中最長的迴文子序列。在一個給定的字元串中，找到最長的迴文子序列，並且返回這個子序列，這就是最長迴文子序列LPS問題。注意和最長迴文子串的區別，最長迴文子串必須是連續的，這裡的最長迴文子序列，可以是不連續的。

思路描述如下：

方法一：動態規劃

假設str[0...n-1]是給定的字元串序列，長度為n，假設表示序列str[0...n-1]的最長迴文子序列的長度。

分為兩種情況考慮：

1.如果str的最後一個元素和第一個元素是相同的，則有：例如字元串序列「AABACACBA」，第一個元素和最後一個元素相同，其中lps(1,n-2)表示加粗部分的最長迴文子序列的長度；

2.如果str的最後一個元素和第一個元素是不相同的，則有：

例如字元串序列「ABACACB」，其中表示去掉第一元素的子序列，表示去掉最後一個元素的子序列。DP採用兩重循環，第一重循環枚舉區間長度，從1到n-1。第二重循環枚舉要考察的區間起點，從0到n-i。於是，我們有如下DP：

演算法時間複雜度O()，空間複雜度O()。

代碼：

//動態規劃求解最長迴文子序列，時間複雜度為O(n^2) int lpsDp(char *str, int n) { int dp[10][10], tmp; memset(dp, 0, sizeof(dp)); for (int i = 0; i < n; ++i) dp[i][i] = 1; for (int i = 1; i < n; ++i) { tmp = 0; //考慮所有連續的長度為i+1的子串，str[j....j+i] for (int j = 0; j + i < n; j++) { //如果首尾相同 if (str[j] == str[j + i]) tmp = dp[j + 1][j + i - 1] + 2; //如果首尾不同 else tmp = max(dp[j + 1][j + i], dp[j][j + i - 1]); dp[j][j + i] = tmp; } } return dp[0][n - 1]; //返回字元串str[0...n-1]的最長迴文子序列長度 }

輸出方法：

如上圖所示，cabbeaf經過DP處理之後得到的dp數組各值，我們輸出的時候只需要掃描兩行即dp[0][k]和dp[k][n-1]，只要發現dp[0][k]與dp[0][k-1]不相等，那麼s[k]就是一個需要的字元，標記一下就可以輸出了。

方法二：轉化為LCS

該問題可以轉化為最長公共子序列問題（Longest Common Subsequence）兩者的處理方法一致。

將原字元串a倒序存入字元串b中，接著對a,b跑LCS即可。

時間和空間複雜度不變，均為O(n2)

第一次寫知乎專欄，感覺插入公式特別麻煩，公式還不能複製，還Word好用。

代碼怎麼高亮呀，老哥們教教我。

推薦閱讀：