leetcode - 516. 最長回文子序列

516. 最長回文子序列

————————————————————————————————————————————

給定一個字元串s，找到其中最長的回文子序列。可以假設s的最大長度為1000。

示例 1:

輸入:

“bbbab”

輸出:

4

一個可能的最長回文子序列為 “bbbb”。

示例 2:

輸入:

“cbbd”

輸出:

2

一個可能的最長回文子序列為 “bb”。

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/longest-palindromic-subsequence

————————————————————————————————————————————

解題思路：

1. 狀态：

   f[i][j] 表示 s 的第 i 個字元到第 j 個字元組成的子串中，最長的回文序列長度是多少。

2. 轉移方程：

   如果 s 的第 i 個字元和第 j 個字元相同的話

   f[i][j] = f[i + 1][j - 1] + 2

   如果 s 的第 i 個字元和第 j 個字元不同的話

   f[i][j] = max(f[i + 1][j], f[i][j - 1])

然後注意周遊順序，i 從最後一個字元開始往前周遊，j 從 i + 1 開始往後周遊，這樣可以保證每個子問題都已經算好了。

初始化

f[i][i] = 1 單個字元的最長回文序列是 1

結果

f[0][n - 1]

作者：a380922457

連結：https://leetcode-cn.com/problems/two-sum/solution/dong-tai-gui-hua-si-yao-su-by-a380922457-3/

來源：力扣（LeetCode）

————————————————————————————————————————————

具體的C++代碼如下所示：

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int length = s.size();
        vector<vector<int>> dp(length,vector<int>(length,0));
        for(int i=length-1;i>=0;i--)
        {
            dp[i][i]=1;
            for(int j=i+1;j<length;j++)
            {
                if(s[i]==s[j])
                    dp[i][j]=dp[i+1][j-1]+2;
                else
                    dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
            }
        }
        return dp[0][length-1];
    }
};