LeetCode 516.最長回文子序列 C++

LeetCode 516.最長回文子序列

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

示例 1:

輸入: “bbbab”

輸出: 4

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

示例 2:

輸入: “cbbd”

輸出: 2

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

提示：

1 <= s.length <= 1000

s 隻包含小寫英文字母

來源：力扣（LeetCode）

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

問題分析： dp[i][j]的含義是s[i]~s[j]的最長回文子序列。

然後進行判斷，如果s[i]==s[j]，那麼dp[i][j]=dp[i+1][j-1]+2

如果s[i]!=s[j]，就想着把s[i]和s[j]分别納入回文子序列，然後判斷誰更長，

是以dp[i][j]=max(dp[i+1][j],dp[i][j-1])

代碼如下：

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n=s.length();
        vector<vector<int>> dp(n,vector<int>(n,0));
        //base case 對角線上的回文子序列長度肯定是1
        for(int i=0;i<n;i++){
            dp[i][i]=1;
        }
        //因為dp[i][j]與左上、左下、正下三個方向有關，是以隻能斜着周遊或反着周遊（這裡是反着周遊）
        for(int i=n-2;i>=0;i--){
            for(int j=i+1;j<n;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][n-1];
    }
};