[打卡]8.12_516.最长回文子序列

参考题解:子序列问题通用思路

相关模板:

int n = arr.length;
int[][] dp = new dp[n][n];

for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
        if (arr[i] == arr[j])
            dp[i][j] = dp[i][j] + ...
        else
            dp[i][j] = 最值(... )
    }
}

• 集合划分
  • 两个目标时:在子数组 arr1[0...i] 和子数组 arr2[0...j] 中，我们要求的子序列的长度为 dp[i][j]
  • 一个目标时:在子数组 arr[i....j] 中，我们要求子序列的长度为dp[i][j]

AC代码：

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));//动态转移数组全为0
        for (int i = 0; i < n; i++) dp[i][i] = 1;//初始化,在s(i,j) 当 i == j 时,只有一个字符(回文串)

        //确保 左、左下、下 的状态能先计算出来,选择向后开始状态转移，参考状态一
        for (int i = n - 1; 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];
    }
};

状态一:

状态二:

状态三:

本文链接：