題目要求 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]; }};新聞熱點
疑難解答
