leetcode 516. 最長回文子序列（區間DP問題）

題目描述

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

示例 1:

輸入:“bbbab”

輸出:4

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

示例 2:

輸入:“cbbd”

輸出:2

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

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

區間DP問題

基本模本如下：首先枚舉區間長度，之後枚舉區間的起始位置。架構如下

其中區間終點計算過程：起點定義為 i ,終點定義為 j 。[i,j] 區間長度為len，是以j-i+1=len，是以 j = i+len-1

for (int len = 1; len <= n; len++) //區間長度
{          
    for (int i = 1; i + len - 1 <= n; i++) //枚舉起點i
    { 
        int j = i + len - 1;                 //區間終點j
        //根據題目寫代碼//
    }
}

           

定義dp[i][j]的含義表示在區間 [i,j] 内回文子序列的最大長度。最後輸出的結果是dp[0][n-1] 表示的是區間0到n-1之間的回文串子序列的最大長度。

對于區間[i,j] 有四種選擇方式（以i，j這兩個端點是不是在區間内來劃分）：

• 選擇區間i ，選擇區間j f[ i + 1 ][ j-1 ]+2，也就是讓區間[i+1,j-1] 内的回文串長度最長。
• 不選擇區間i ，選擇區間j f[ i +1 ][ j ]
• 選擇區間i ，不選擇區間j f[ i ][ j-1 ]
• 二者都不選擇 f[ i +1 ][ j-1 ]
  • 其中 f[ i +1 ][ j ]和 f[ i ][ j-1 ]都是包含 f[ i +1 ][ j-1 ]的。原因可以看表達式。（建議換條直線了解下标）

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