算尽天下|算法|题解

[算尽天下系列第7期]LeetCode·516·最长回文子序列

jxtxzzw · 3月1日 · 2020年 · · 112次已读

LeetCode 516 最长回文子序列

题目描述

给定一个字符串 s,找到其中最长的回文子序列。可以假设 s 的最大长度为 1000。

样例

样例输入1

bbbab

样例输出1

4

样例解释1

一个可能的最长回文子序列为 bbbb

样例输入2

cbbd

样例输出2

2

样例解释2

一个可能的最长回文子序列为 bb

算法与数据结构

动态规划

题解

再多看几道动态规划的题目,长老就要和大家分享微软、字节跳动等大公司笔试中的动态规划真题啦,所以大家一定要认真消化这几题哦。

最长回文子序列也是动态规划中的经典题目,这次不再是线性规划了,而是二维矩阵,不过理解起来也很容易。

回顾线性规划中,我们往往定义 dp[i] 为到 i 为止符合题目要求的解的值,而在二维动态规划中,我们往往定义 dp[i][j] 表示从 i 到 j 这一段中符合题目要求的解的值。

例如对于这道题,我们定义 dp[i][j] 表示字符串从 i 到 j 的子串中,最长子序列的长度。最终,dp[0][n - 1] 就是答案。

那么,状态转移呢?

为了得到 dp[i][j],我们可以考察 s[i]s[j],如果这两个位置上的字符是一样的,那么显然,dp[i][j] = dp[i + 1][j - 1] + 2

如果这两个位置上的字符是不一样,那么,取 dp[i + 1][j]dp[i][j - 1] 中较大的即可。

最后考虑初始条件,初始条件就是当长度为 1 时,自然成为回文序列,于是,dp[i][i] = 1 对任意的 i 成立。

但是在写代码的时候,我们需要注意,这里数组下标的循环并不能简单从 1 循环到 n:

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        // TODO
    }
}

通过简单比对样例输入输出可以很容易发现,状态转移并不是随着下标推进的,而是随着下标之间的距离(即 i 和 j 之间的距离)推进的:我们首先得到了 dp[i][i] 的值,都等于 1,也就是所有长度为 1 的子串,我们得到了它的最长回文子序列的长度,下面应该去计算所有长度为 2 的子串,再长度为 3 的子串……只有这样,我们比较 s[i]s[j] 才是有意义的。

所以,一种常见的技巧就是以跨度 len 为外层循环,以下标 i 为内层循环,在循环内计算下标 j

for (int len = 1; len <= length; len++) {
    for (int i = 0; i + len - 1 < length; i++) {
        int j = i + len - 1;
        // TODO
    }
}

完整代码

int length = s.length();
int[][] dp = new int[length][length];
for (int len = 1; len <= length; len++) {
    for (int i = 0; i + len - 1 < length; i++) {
        int j = i + len - 1;
        if (i == j) {
            dp[i][j] = 1;
        } else {
            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
}
return dp[0][length - 1];

共 2 条评论
说点什么

avatar

您可以根据需要插入表情、图片、音频、视频或者其他附件,也可以 @ 你需要提及的用户

  
不开心么么什么再见加油发火可以可怜可爱吐吐血吓呵呵哈哈哦哭哼喜欢嗯嘿嘿困圣诞坏笑圣诞调皮坏笑女汉子奸笑好的委屈宝宝害羞小清新心塞快哭了恭喜发财惆怅我最美抓狂抠鼻放空无奈晕汗泪奔温柔女生狗年生气笑笑泪衰调皮调皮女生鄙视酷静静额鼓掌
上传图片
 
 
 
上传视频和音频
 
 
 
上传其他类型文件
 
 
 
1 评论主题数
1 评论回复数
0 评论跟进人数
 
最近回复的评论
最热烈的讨论
1 评论人数
Robin 最近评论者

  订阅评论动态  
最新 最旧 得票最多
提醒
    Robin
    Robin
    离线
    1 月 之前 [2020-3-2 · 9:34]
    Chrome 80.0.3987.87 Windows 10

    c++代码

    int longestPalindromeSubseq(string s) {
    int n = s.size();
    vector< vector > dp(n, vector(n, 0));
    for(int i=n-1; i>=0; i–){
    dp[i][i] = 1;
    for(int j=i+1; j>n; j++){
    if(s[i] == s[j]){
    // dp[i][j] = max(dp[i][j], dp[i+1][j-1]+2);
    dp[i][j] = dp[i+1][j-1]+2;
    }
    else{
    // dp[i][j] = max(dp[i][j], max(dp[i+1][j], dp[i][j-1]));
    dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
    }
    }
    }
    return dp[0][n-1];
    }

      Robin
      Robin
      离线
      1 月 之前 [2020-3-2 · 9:35]
      Chrome 80.0.3987.87 Windows 10

      代码块又出问题了- –