LeetCode Longest Palindromic Subsequence Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000. Example 1: Input:

"bbbab"

Output:

4

One possible longest palindromic subsequence is “bbbb”. Example 2: Input:

"cbbd"

Output:

2

One possible longest palindromic subsequence is “bb”.

---

求一个字符串的最长回文子序列。 使用DP求解，假设dp[i][j]表示原字符串范围[i,j]中的最长回文子序列的长度。则如果s[i]==s[j]，则dp[i][j]=dp[i+1][j-1]+2，即是临近内层的最长回文子序列长度加2。如果s[i]!=s[j]，则dp[i][j]=max(dp[i][j-1],dp[i+1][j])，即是左端或者右端最长回文子序列长度的最大值。 初始时dp[i][i]=1，即单个字符自成回文，长度为1。 代码如下： [cpp] class Solution2 { public: int longestPalindromeSubseq(string s) { int n = s.size(); vector<vector<int>> dp(n, vector<int>(n, 0)); for (int i = n – 1; i >= 0; –i) { dp[i][i] = 1; 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][j – 1], dp[i + 1][j]); } } return dp[0][n – 1]; } }; [/cpp] 本代码提交AC，用时68MS。 上述计算有些区间会重复计算dp[i][j]，可以用递归方法求解，并且把计算过的值记录下来，下次遇到查询时直接返回。代码如下： [cpp] class Solution { private: int helper(int l, int r, const string &s, vector<vector<int>> &dp) { if (l > r)return 0; if (l == r)return 1; if (dp[l][r] != 0)return dp[l][r]; if (s[l] == s[r])dp[l][r] = helper(l + 1, r – 1, s, dp) + 2; else dp[l][r] = max(helper(l, r – 1, s, dp), helper(l + 1, r, s, dp)); return dp[l][r]; } public: int longestPalindromeSubseq(string s) { int n = s.size(); vector<vector<int>> dp(n, vector<int>(n, 0)); return helper(0, n – 1, s, dp); } }; [/cpp] 本代码提交AC，用时49MS。 参考：https://discuss.leetcode.com/topic/78603/straight-forward-java-dp-solution/2]]>