首页 星云 工具 资源 星选 资讯 热门工具
:

PDF转图片 完全免费 小红书视频下载 无水印 抖音视频下载 无水印 数字星空

线性dp:LeetCode516 .最长回文子序列

编程知识
2024年09月07日 15:18

LeetCode516 .最长回文子序列

题目叙述:

力扣题目链接(opens new window)

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

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

示例 1:

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

示例 2:

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

提示:

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

动态规划思路

  • 我们在上文中已经介绍了回文子串,那么我们可以沿用回文子串的思想解决这道题,但是我们首先得明确回文子串回文子序列的区别

  • LeetCode647.回文子串求的是回文子串,而本题要求的是回文子序列, 要搞清楚这两者之间的区别。

  • 回文子串是要连续的,回文子序列可不是连续的! 回文子串,回文子序列都是动态规划经典题目。

  • 回文子串,可以做这两题:

    • 647.回文子串

    • 5.最长回文子串

思路其实是差不多的,但本题要比求回文子串简单一点,因为情况少了一点。

动规五部曲分析如下:

1.确定状态变量及其含义

  • 我们设立dp数组,dp[i]] [j] 表示s字符串在[i,j]范围内最长回文子序列的长度。(j>=i
  • 那么我们确立了状态变量dp[i][j],那么我们就要开始处理递推公式和如何初始化了

2.确定递推公式

  • 在这里,我们最重要的就是判断s[i],s[j]之间的关系
    • s[i]==s[j] 此时,dp[i][j]=dp[i+1][j-1]+2
  • 为什么是+2呢?因为本题是最长回文子序列,当s[i]==s[j]时,[i,j]范围内至少有dp[i+1][j-1]+2这个大小的最长回文子序列,+2就是加上s[i],s[j]这两个字符。

516.最长回文子序列

  • 如果s[i]与s[j]不相同,说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子序列的长度,那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。

加入s[j]的回文子序列长度为dp[i + 1] [j]

加入s[i]的回文子序列长度为dp[i] [j - 1]

那么dp [i] [j]一定是取最大的,即:dp [i] [j] = max(dp [i + 1] [j], dp[i] [j - 1]);

516.最长回文子序列1

3.如何初始化dp数组

  • 首先,我们得处理特殊情况,当i==j的时候,这个时候在[i,j]范围内只有一个字符,使用dp[i][j]=dp[i+1][j-1]+2 会导致当前处理的子串的左边界大于右边界,此时我们就得特殊处理一下,当处理的子串只有一个字符时,i==j,并且dp[i][j]显然等于1,因为单个字符也是回文子序列,并且这个回文子序列的长度是1。
vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
for (int i = 0; i < s.size(); i++) dp[i][i] = 1;

4. 确定遍历顺序

从递归公式中,可以看出,dp[i][j] 依赖于 dp[i + 1][j - 1] dp[i + 1][j] 和 dp[i][j - 1],如图:

img

  • 所以说我们想要得到dp[i][j] ,必须从左下方开始,向着右上方的方向进行递推。
  • 所以说遍历顺序就是从下到上,从左到右
        //开始对dp数组进行从下到上,从左到右进行赋值。
        for(int i=s.size()-1;i>=0;i--){
            for(int j=i+1;j<s.size();j++){
                if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1]+2;
                else dp[i][j]=max(dp[i][j-1],dp[i+1][j]);
            }
        }

5.举例打印dp数组

输入s:"cbbd" 为例,dp数组状态如图:

516.最长回文子序列3

红色框即:dp[0][s.size() - 1]; 为最终结果。

最终代码:

//最长回文子序列
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        //创建二维的dp数组
        vector<vector<int>> dp(s.size(),vector<int>(s.size(),0));
        //初始化dp数组,首先要将i和j相等的时候,也就是只有一个字符的子序列,它的dp值赋值为1
        for(int i=0;i<s.size();i++) dp[i][i]=1;
        //开始对dp数组进行从下到上,从左到右进行赋值。
        for(int i=s.size()-1;i>=0;i--){
            for(int j=i+1;j<s.size();j++){
                if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1]+2;
                else dp[i][j]=max(dp[i][j-1],dp[i+1][j]);
            }
        }
        //最后,从0-s.size()-1这个范围的最长回文子序列的长度就是我们需要的答案。
        return dp[0][s.size()-1];
    }
};

注明

  • 本文中引用了作者代码随想录的部分图片和原文,若想深入了解,可以去原作者的文章阅读
  • 代码随想录
From:https://www.cnblogs.com/Tomorrowland/p/18401821
本文地址: http://www.shuzixingkong.net/article/1814
0评论
提交 加载更多评论
其他文章 使用 `Roslyn` 分析器和修复器对.cs源代码添加头部注释
之前写过两篇关于Roslyn源生成器生成源代码的用例,今天使用Roslyn的代码修复器CodeFixProvider实现一个cs文件头部注释的功能, 代码修复器会同时涉及到CodeFixProvider和DiagnosticAnalyzer, 实现FileHeaderAnalyzer 首先我们知道修
使用 `Roslyn` 分析器和修复器对.cs源代码添加头部注释 使用 `Roslyn` 分析器和修复器对.cs源代码添加头部注释 使用 `Roslyn` 分析器和修复器对.cs源代码添加头部注释
五子棋AI:实现逻辑与相关背景探讨(下)
前文回顾 在上篇文章中,我们约定了一种衡量格子价值的方式,如下表。 综合价值排序 己方价值 敌方价值 对应的奖励数值 1 Lv1 ? \(2^{20}\) 2 ? Lv1 \(2^{16}\) 3 Lv2 ? \(2^{12}\) 4 ? Lv2 \(2^{8}\) 5 Lv3 ? \(2^{4}\
Java是值传递还是引用传递,又是怎么体现的
关于Java是值传递还是引用传递,可以从代码层面来实现一下拿到结果 执行下面的代码: public static void main(String[] args) { int num = 10; String name = &quot;Tom&quot;; modify(num, name); Sy
跳跃表
概述 跳跃表(SkipList)是链表加多级索引组成的数据结构。链表的数据结构的查询复条度是 O(N)。为了提高查询效率,可以在链表上加多级索引来实现快速查询。跳跃表不仅能提高搜索性能。也能提高插入和删除操作的性能。索引的层数也叫作跳跃表的高度 查找 在跳跃表的结构中会首先从顶层开始查找,当顶层不存
跳跃表 跳跃表 跳跃表
XGBoost模型 0基础小白也能懂(附代码)
XGBoost 是 eXtreme Gradient Boosting 的缩写称呼,它是一个非常强大的 Boosting 算法工具包,优秀的性能(效果与速度)让其在很长一段时间内霸屏数据科学比赛解决方案榜首,现在很多大厂的机器学习方案依旧会首选这个模型。
XGBoost模型 0基础小白也能懂(附代码) XGBoost模型 0基础小白也能懂(附代码) XGBoost模型 0基础小白也能懂(附代码)
Kafka原理剖析之「Topic创建」
一、前言 Kafka提供了高性能的读写,而这些读写操作均是操作在Topic上的,Topic的创建就尤为关键,其中涉及分区分配策略、状态流转等,而Topic的新建语句非常简单 bash kafka-topics.sh \ --bootstrap-server localhost:9092 \ // 需
Kafka原理剖析之「Topic创建」 Kafka原理剖析之「Topic创建」 Kafka原理剖析之「Topic创建」
【Azure Developer】上手 The Best AI Code "Cursor" : 仅仅7次对话,制作个人页面原型,效果让人惊叹!
AI Code 时代早已开启,自己才行动。上手一试,让人惊叹。借助这感叹的情绪,把今天操作Cursor的步骤记录下来,也分享给大家。 推荐大家上手一试,让你改变! 准备阶段 下载 Cursor(https://www.cursor.com/),点击右上角“Download”下载exe安装文件。 安装
【Azure Developer】上手 The Best AI Code "Cursor" : 仅仅7次对话,制作个人页面原型,效果让人惊叹! 【Azure Developer】上手 The Best AI Code "Cursor" : 仅仅7次对话,制作个人页面原型,效果让人惊叹! 【Azure Developer】上手 The Best AI Code "Cursor" : 仅仅7次对话,制作个人页面原型,效果让人惊叹!
代码整洁之道--读书笔记(4)
代码整洁之道 简介: 本书是编程大师“Bob 大叔”40余年编程生涯的心得体会的总结,讲解要成为真正专业的程序员需要具备什么样的态度,需要遵循什么样的原则,需要采取什么样的行动。作者以自己以及身边的同事走过的弯路、犯过的错误为例,意在为后来者引路,助其职业生涯迈上更高台阶。 本书适合所有程序员阅读,
代码整洁之道--读书笔记(4) 代码整洁之道--读书笔记(4)