LeetCode 516 Longest Palindromic Subsequence
概述
https://leetcode.com/problems/longest-palindromic-subsequence/
动态规划法
极值问题，你知道我要说什么了吧？
回文子串，我们为了方便应该从起点下手。
开玩笑，应该从两头下手。
class Solution {
public:
int longestPalindromeSubseq(string s) {
vector<vector<int>> dp(s.size(), vector<int>(s.size(), -1));
return helper(dp, s, 0, s.size() - 1);
}
int helper(vector<vector<int>>& dp, string& s, int l, int r) {
if (l == r) return 1;
if (l > r) return 0;
if (dp[l][r] != -1) return dp[l][r];
if (s[l] == s[r]) {
dp[l][r] = 2 + helper(dp, s, l + 1, r - 1);
} else {
dp[l][r] = max(helper(dp, s, l + 1, r), helper(dp, s, l, r - 1));
}
return dp[l][r];
}
};