[Leetcode 516] Longest Palindromic Subsequence

作者 Shilei Tian 日期 2017-02-10
[Leetcode 516] 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[i][j] 来表示从 ij 这一段子串中最长回文子串的长度,那么 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])

从状态转移方程中我们可以看到,每次对于 dp 的第一个维度,我们只需要后面或者是当前这个维度即可,因此 i 应该是从后向前遍历;而对于第二个维度, j 需要的是当前或者前面的维度,所以 j 应该正序遍历。代码如下:

class Solution {
public:
int longestPalindromeSubseq(string s) {
vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
for (int i = 0; i < s.size(); ++i) {
dp[i][i] = 1;
}
for (int i = s.size() - 1; i >= 0; --i) {
for (int j = i + 1; j < s.size(); ++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][s.size() - 1];
}
};