算法|题解

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

凝神长老 · 3月1日 · 2020年 · · 564次已读

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 投票
文章评分
订阅评论动态
提醒
guest
2 评论
最新
最旧 得票最多
行内反馈
查看所有评论
Robin
Robin Chrome 80.0.3987.87 Windows 10
2020年3月2日 09:34

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 Chrome 80.0.3987.87 Windows 10
回复  Robin
2020年3月2日 09:35

代码块又出问题了- –