zl程序教程

您现在的位置是:首页 >  其他

当前栏目

【面试高频题】难度 2/5,经典区间 DP 模板题(详解如何思考区间 DP 问题)

2023-02-19 12:17:52 时间

题目描述

这是 LeetCode 上的「516. 最长回文子序列」,难度为「中等」

Tag : 「动态规划」、「区间 DP」

给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。

子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。

示例 1:

输入:s = "bbbab"

输出:4

解释:一个可能的最长回文子序列为 "bbbb" 。

示例 2:

输入:s = "cbbd"

输出:2

解释:一个可能的最长回文子序列为 "bb" 。

提示:

  • 1 <= s.length <= 1000
  • s 仅由小写英文字母组成

动态规划

这是一道经典的区间 DP 题。

之所以可以使用区间 DP 进行求解,是因为在给定一个回文串的基础上,如果在回文串的边缘分别添加两个新的字符,可以通过判断两字符是否相等来得知新串是否回文。

也就是说,使用小区间的回文状态可以推导出大区间的回文状态值。

从图论意义出发就是,任何一个长度为 len的回文串,必然由「长度为 len - 1」或「长度为 len - 2」的回文串转移而来。

两个具有公共回文部分的回文串之间存在拓扑序(存在由「长度较小」回文串指向「长度较大」回文串的有向边)。

通常区间 DP 问题都是,常见的基本流程为:

需要说明的是,上述几种情况可以确保我们做到「不漏」,但不能确保「不重」,对于求最值问题,我们只需要确保「不漏」即可,某些状态重复参与比较,不会影响结果的正确性。

❝一些细节:我们需要特判掉长度为 1和 2的两种基本情况。当长度为 1 时,必然回文,当长度为 2 时,当且仅当两字符相等时回文。 ❞

代码:

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();
        int[][] f = new int[n][n]; 
        for (int len = 1; len <= n; len++) {
            for (int l = 0; l + len - 1 < n; l++) {
                int r = l + len - 1;
                if (len == 1) {
                    f[l][r] = 1;
                } else if (len == 2) {
                    f[l][r] = cs[l] == cs[r] ? 2 : 1;
                } else {
                    f[l][r] = Math.max(f[l + 1][r], f[l][r - 1]);
                    f[l][r] = Math.max(f[l][r], f[l + 1][r - 1] + (cs[l] == cs[r] ? 2 : 0));
                }
            }
        }
        return f[0][n - 1];
    }
}
  • 时间复杂度:O(n^2)
  • 空间复杂度:O(n^2)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.516 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。