【範例】區間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);
}
};