【刷穿 LeetCode】516. 最长回文子序列 : 区间 DP 求解最长回文子序列问题

简介: 【刷穿 LeetCode】516. 最长回文子序列 : 区间 DP 求解最长回文子序列问题

网络异常,图片无法展示
|


题目描述



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


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


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


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


示例 1:


输入:s = "bbbab"
输出:4
解释:一个可能的最长回文子序列为 "bbbb" 。
复制代码

示例 2:

输入:s = "cbbd"
输出:2
解释:一个可能的最长回文子序列为 "bb" 。
复制代码


提示:


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


动态规划



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


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


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


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


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


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


  1. 从小到大枚举区间大小 lenlen
  2. 枚举区间左端点 ll,同时根据区间大小 lenlen 和左端点计算出区间右端点 r = l + len - 1r=l+len1
  3. 通过状态转移方程求 f[l][r]f[l][r] 的值


因此,我们 定义 f[l][r]f[l][r] 为考虑区间 [l, r][l,r] 的最长回文子序列长度为多少。

不失一般性的考虑 f[l][r]f[l][r] 该如何转移。


由于我们的状态定义 没有限制 回文串中必须要选 s[l]s[l] 或者 s[r]s[r]


我们对边界字符 s[l]s[l]s[r]s[r] 分情况讨论,最终的 f[l][r]f[l][r] 应该在如下几种方案中取 maxmax


  • 形成的回文串一定不包含 s[l]s[l]s[r]s[r],即完全不考虑 s[l]s[l]s[r]s[r]

f[l][r] = f[l + 1][r - 1]f[l][r]=f[l+1][r1]

  • 形成的回文串可能包含 s[l]s[l],但一定不包含 s[r]s[r]

f[l][r] = f[l][r - 1]f[l][r]=f[l][r1]

  • 形成的回文串可能包含 s[r]s[r],但一定不包含 s[l]s[l]

f[l][r] = f[l + 1][r]f[l][r]=f[l+1][r]

  • 形成的回文串可能包含 s[l]s[l],也可能包含 s[r]s[r],根据 s[l]s[l]s[r]s[r] 是否相等:


f[l][r] = \begin{cases} f[l + 1][r - 1] + 2 & s[l] = s[r] \\ f[l + 1][r - 1] & s[l] \neq s[r] \\ \end{cases}f[l][r]={f[l+1][r1]+2f[l+1][r1]s[l]=s[r]s[l]=s[r]


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


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


代码:


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(n2)
  • 空间复杂度:O(n^2)O(n2)


最后



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


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


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


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

相关文章
|
4天前
|
存储
力扣-2904最短且字典序最小的美丽子序列
力扣-2904最短且字典序最小的美丽子序列
6 1
|
5天前
|
存储 算法 数据可视化
【模拟面试问答】深入解析力扣163题:缺失的区间(线性扫描与双指针法详解)
【模拟面试问答】深入解析力扣163题:缺失的区间(线性扫描与双指针法详解)
|
5天前
|
存储 算法 数据可视化
哈希表法快速求解最长连续序列 | 力扣128题详细解析
哈希表法快速求解最长连续序列 | 力扣128题详细解析
|
5天前
|
存储 自然语言处理 算法
LeetCode题目115:不同子序列
LeetCode题目115:不同子序列
|
5天前
|
存储 SQL 算法
高效日程管理:利用区间合并算法优化活动安排【python LeetCode57】
高效日程管理:利用区间合并算法优化活动安排【python LeetCode57】
|
5天前
|
存储 算法 搜索推荐
掌握区间合并:解决实际问题的算法策略和应用案例【python LeetCode题目56】
掌握区间合并:解决实际问题的算法策略和应用案例【python LeetCode题目56】
|
9天前
dp表,哈希表,力扣5.最长回文子串力扣1745.分割回文串IV力扣132.分割回文串II优先级队列(堆)是什么下面是手动实现小根堆力扣1046.最后一块石头的重量
dp表,哈希表,力扣5.最长回文子串力扣1745.分割回文串IV力扣132.分割回文串II优先级队列(堆)是什么下面是手动实现小根堆力扣1046.最后一块石头的重量
|
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
|
19天前
|
索引
【力扣刷题】两数求和、移动零、相交链表、反转链表
【力扣刷题】两数求和、移动零、相交链表、反转链表
22 2
【力扣刷题】两数求和、移动零、相交链表、反转链表