本文写于 2020年03月01日,距今已超过 1 年,距 2020年03月26日 的最后一次修改也已超过 3 个月,部分内容可能已经过时,您可以按需阅读。如果图片无法显示或者下载链接失效,请给我反馈,谢谢!


0 0 投票数
评分

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];
0 0 投票数
评分