leetcode 516 最长回文子序列

简介: leetcode 516 最长回文子序列

最长回文子序列

和647类似

c610afed07bc43d888cbfcaae6ec334c.png

动态规划

  • 确定dp数组(dp table)以及下标的含义
    dp[i][j]:字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。
  • 确定递推公式
    在判断回文子串的题目中,关键逻辑就是看s[i]与s[j]是否相同。

如果s[i]与s[j]相同,

  • j - i ==0 , dp[i][j] = 1;
  • j - i == 1, dp[i][j] = 2;
  • j - i > 2, dp[i][j] = dp[i + 1][j - 1] + 2;

1042b45ce7714e2997c6c74abab8c25e.png

  • 如果s[i]与s[j]不同
    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

fe6bacb19f8444adb9e54b633c8207fc.png

确定遍历顺序

从递推公式dp[i][j] = dp[i + 1][j - 1] + 2 和 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) 可以看出,dp[i][j]是依赖于dp[i + 1][j - 1] 和 dp[i + 1][j],

也就是从矩阵的角度来说,dp[i][j] 下一行的数据。 所以遍历i的时候一定要从下到上遍历,这样才能保证,下一行的数据是经过计算的。


d988b3e3658b4de8bdb785005d6ffa7b.png

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        if(s.size()<=1) return s.size();
        vector<vector<int>> dp(s.size() , vector<int>(s.size() ,0));
        int result = 0;
        for(int i=s.size()-1; i>=0 ;i-- )
            for(int j=i ;j<s.size();j++)
            {
                if(s[i]==s[j])
                {
                    if(j==i) dp[i][j] = 1;
                    else if(j-i==1) dp[i][j] = 2;
                    else dp[i][j] = dp[i+1][j-1] + 2;
                    if(dp[i][j] > result) result = dp[i][j];
                }else
                {
                    dp[i][j] = max(dp[i][j-1],dp[i+1][j]);
                }
            }
        // for(int i=0;i<s.size();i++)
        // {
        //     for(int j=0;j<s.size();j++)
        //     cout<<dp[i][j]<<' ';
        //     cout<<endl;
        // }
        return result;
    }
};

二刷

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>> dp(s.size() , vector<int>(s.size() ,0 ));
        for(int i=s.size()-1 ; i>=0 ;i--)
        {
            for(int j=i ; j<s.size() ;j++)
            {
                if(s[i]==s[j])
                {
                    if(j-i == 0) dp[i][j] = 1;
                    else if(j-i == 1) dp[i][j] = 2;
                    else dp[i][j] = dp[i+1][j-1] +2;
                }else dp[i][j] = max(dp[i+1][j-1] , max(dp[i+1][j] , dp[i][j-1]));
            }
        }
        return dp[0][s.size()-1];
    }
};
相关文章
|
4天前
|
存储
力扣-2904最短且字典序最小的美丽子序列
力扣-2904最短且字典序最小的美丽子序列
6 1
|
5天前
|
存储 算法 数据可视化
哈希表法快速求解最长连续序列 | 力扣128题详细解析
哈希表法快速求解最长连续序列 | 力扣128题详细解析
|
5天前
|
存储 自然语言处理 算法
LeetCode题目115:不同子序列
LeetCode题目115:不同子序列
|
9天前
|
Java
贪心 -力扣860.柠檬水找零力扣2208.将数组和减半的最少操作次数力扣179.最大数力扣376.摆动序列
贪心 -力扣860.柠檬水找零力扣2208.将数组和减半的最少操作次数力扣179.最大数力扣376.摆动序列
|
9天前
|
算法 Java Go
【经典算法】LeetCode 392 判断子序列(Java/C/Python3/Go实现含注释说明,Easy)
【经典算法】LeetCode 392 判断子序列(Java/C/Python3/Go实现含注释说明,Easy)
14 0
|
1月前
leetcode代码记录(最长连续递增序列
leetcode代码记录(最长连续递增序列
17 2
|
1月前
leetcode代码记录(最长递增子序列
leetcode代码记录(最长递增子序列
13 1
|
1月前
|
算法
leetcode代码记录(摆动序列
leetcode代码记录(摆动序列
16 0
|
1月前
|
算法
代码随想录算法训练营第五十六天 | LeetCode 647. 回文子串、516. 最长回文子序列、动态规划总结
代码随想录算法训练营第五十六天 | LeetCode 647. 回文子串、516. 最长回文子序列、动态规划总结
37 1
|
1月前
|
测试技术
【力扣】392.判断子序列
【力扣】392.判断子序列