leetcode 516. Longest Palindromic Subsequence 最长回文子序列 + DP动态规划

谁借莪１个温暖的怀抱￠ 2022-06-03 03:10 138阅读 0赞

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动态规划

建议和这一道题一起学习[leetcode 5. Longest Palindromic Substring 最长回文子串的查找 + 按照length做DP][leetcode 5. Longest Palindromic Substring _ _ _length_DP] 和[leetcode 730. Count Different Palindromic Subsequences 动态规划DP][leetcode 730. Count Different Palindromic Subsequences _DP]，[leetcode 647. Palindromic Substrings 回文子串的数量][leetcode 647. Palindromic Substrings]

dp\[i\]\[j\]表示字符串i～j下标所构成的子串中最长回文子串的长度～最后我们需要返回的是dp\[0\]\[len-1\]的值

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    
    using namespace std;
    
    
    class Solution
    {
    public:
        int longestPalindromeSubseq(string s)
        {
            vector<vector<int>> dp(s.length(), vector<int>(s.length(), 0));
            for (int i = 0; i < s.length(); i++)
                dp[i][i] = 1;
    
            for (int len = 1; len <= s.length(); len++)
            {
                for (int i = 0; i + len < s.length(); i++)
                {
                    int j = i + len;
                    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.length() - 1];
        }
    };

[leetcode 5. Longest Palindromic Substring _ _ _length_DP]: http://blog.csdn.net/jackzhang_123/article/details/77712863
[leetcode 730. Count Different Palindromic Subsequences _DP]: http://blog.csdn.net/jackzhang_123/article/details/78889242
[leetcode 647. Palindromic Substrings]: http://blog.csdn.net/jackzhang_123/article/details/78862865