【題解】LeetCode 516. Longest Palindromic Subsequence

【範例】區間DP
【題目敘述】https://leetcode.com/problems/longest-palindromic-subsequence/

  • 在起點和終點之間,找區間最大長度。
  • 遞迴終止條件:
    • l = r:dp[l][r] = 1
    • l > r:dp[l][r] = 0
  • 當起點和中點的字母相同時,同時把左界右界同時向內縮,dp[l][r] = dp[l+1][r-1] + 2。
  • 否則,把左界「或」右界向內縮,取其中最大值。
  • (Line-7) ~dp[i][j]:判斷dp[i][j]不是 -1。
    • -1 = b’11111111
    • ~(-1) = b’00000000 -> false
class Solution {
public:
    string str;
    int dp[1005][1005];
    int func(int l, int r){
        if (~dp[l][r]) return dp[l][r];
        if (l == r) return dp[l][r] = 1;
        if (l > r) return dp[l][r] = 0;
        if (str[l] == str[r]) return dp[l][r] = func(l+1, r-1)+2;
        return dp[l][r] = max(func(l+1, r), func(l, r-1));
    }
    int longestPalindromeSubseq(string s) {
        str = s;
        memset(dp, -1, sizeof(dp));
        return func(0, s.length()-1);
    }
};
分享本文 Share with friends