题目要求 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[i][j] 来表示从 i 到 j 这一段子串中最长回文子串的长度，那么 dp[0][s.size() - 1] 就是我们最终想要的结果。
那么状态转移方程应该如何写呢？给定一长度为 l 的字符串，我们想要判断它是否包含回文子串，我们需要做的是：判断 s[i] 和 s[j] 是否相等。如果相等，那么就说明这两个元素是在回文子串中的，那么这个子串的长度就变成了2 + dp[i + 1][j - 1]了，也就是前后两个元素加上去掉这两个元素剩下子串中最长回文子串的长度了。那么如果这两个不相等呢？那么我们就需要检查长度比它小 1 的子串了，一共有两个——去头的和去尾的，这两个到时候选一个大的就行了。
所以，最终的状态转移方程是：
当 s[i] = s[j] 时，dp[i][j] = 2 + dp[i + 1][j - 1]；否则，dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])。代码：
class Solution {public: int longestPalindromeSubseq(string s) { int len = s.length(); vector<vector<int>> dp(len, vector<int>(len)); for (int i = len - 1; i >= 0; i--) { dp[i][i] = 1; for (int j = i + 1; j < len; 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][len-1]; }};新闻热点
疑难解答
