算法沉淀——动态规划之两个数组的 dp(上)(leetcode真题剖析)

在这里插入图片描述

算法沉淀——动态规划之两个数组的 dp

  • 01.最长公共子序列
  • 02.不相交的线
  • 03.不同的子序列
  • 04.通配符匹配

01.最长公共子序列

题目链接:https://leetcode.cn/problems/longest-common-subsequence/

给定两个字符串 text1text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0

一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。

  • 例如,"ace""abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1:

输入:text1 = "abcde", text2 = "ace" 
输出:3  
解释:最长公共子序列是 "ace" ,它的长度为 3 。

示例 2:

输入:text1 = "abc", text2 = "abc"
输出:3
解释:最长公共子序列是 "abc" ,它的长度为 3 。

示例 3:

输入:text1 = "abc", text2 = "def"
输出:0
解释:两个字符串没有公共子序列,返回 0 。 

提示:

  • 1 <= text1.length, text2.length <= 1000
  • text1text2 仅由小写英文字符组成。

思路

状态转移方程:

  1. 如果当前字符相同(text1[i] == text2[j]),说明我们找到了一个新的公共字符,因此最长公共子序列的长度在之前的基础上加 1:
    • dp[i][j] = dp[i - 1][j - 1] + 1
  2. 如果当前字符不同(text1[i] != text2[j]),则我们需要考虑去掉 text1[i] 或者去掉 text2[j] 之后的最长公共子序列。这可以通过比较 text1 的前 i-1 个字符和 text2 的前 j 个字符的最长公共子序列长度,以及 text1 的前 i 个字符和 text2 的前 j-1 个字符的最长公共子序列长度,取最大值:
    • dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

初始化:为了方便处理边界情况,我们在文本 text1text2 前各添加一个空字符,即 text1[0]text2[0] 表示空串。这样,dp 表的大小为 (m+1) x (n+1),其中 mn 分别是两个文本的长度。初始化时,将第一行和第一列的值都设置为 0。

填表顺序:最终的结果存储在 dp[m][n] 中,其中 mn 是两个文本的长度。这个值表示 text1text2 的最长公共子序列的长度。

代码

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m=text1.size(),n=text2.size();

        text1=" "+text1,text2=" "+text2;
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++)
                if(text1[i]==text2[j]) dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

        return dp[m][n];
    }
};

02.不相交的线

题目链接:https://leetcode.cn/problems/uncrossed-lines/

在两条独立的水平线上按给定的顺序写下 nums1nums2 中的整数。

现在,可以绘制一些连接两个数字 nums1[i]nums2[j] 的直线,这些直线需要同时满足满足:

  • nums1[i] == nums2[j]
  • 且绘制的直线不与任何其他连线(非水平线)相交。

请注意,连线即使在端点也不能相交:每个数字只能属于一条连线。

以这种方法绘制线条,并返回可以绘制的最大连线数。

示例 1:

输入:nums1 = [1,4,2], nums2 = [1,2,4]
输出:2
解释:可以画出两条不交叉的线,如上图所示。 
但无法画出第三条不相交的直线,因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。

示例 2:

输入:nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
输出:3

示例 3:

输入:nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
输出:2 

提示:

  • 1 <= nums1.length, nums2.length <= 500
  • 1 <= nums1[i], nums2[j] <= 2000

思路

如果我们希望确保两条直线不相交,我们可以将问题转化为在两个整数数组中寻找最长的公共子序列。这是因为,如果两条直线不相交,它们在同一列上对应的两个元素在两个数组中的顺序关系应该保持一致。

这个问题可以用动态规划来解决,具体步骤如下:

  1. 状态表达
    • 我们选取两个数组分别表示两条直线,数组长度分别为 mn
    • 定义状态表 dp,其中 dp[i][j] 表示数组1的前 i 个元素和数组2的前 j 个元素中的最长公共子序列的长度。
  2. 状态转移方程
    • 如果 nums1[i] == nums2[j],说明找到了一个公共元素,状态转移方程为 dp[i][j] = dp[i-1][j-1] + 1
    • 如果 nums1[i] != nums2[j],则需要在两个数组的前面部分分别寻找最长公共子序列,状态转移方程为 dp[i][j] = max(dp[i-1][j], dp[i][j-1])
  3. 初始化
    • 为了方便处理边界情况,可以在两个数组的前面各添加一个虚拟元素,表示空串。
    • 初始化 dp 数组的第一行和第一列为0,因为空串与任何数组的最长公共子序列长度都为0。
  4. 填表顺序
    • 从上到下,从左到右填写 dp 数组。
  5. 返回值
    • 最终的结果存储在 dp[m][n] 中,表示两个数组的最长公共子序列的长度。

代码

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int m=nums1.size(),n=nums2.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++)
                if(nums1[i-1]==nums2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

        return dp[m][n];
    }   
};

03.不同的子序列

题目链接:https://leetcode.cn/problems/distinct-subsequences/

你两个字符串 st ,统计并返回在 s子序列t 出现的个数,结果需要对 109 + 7 取模。

示例 1:

输入:s = "rabbbit", t = "rabbit"
输出:3
解释:
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

示例 2:

输入:s = "babgbag", t = "bag"
输出:5
解释:
如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
babgbag
babgbag
babgbag
babgbag
babgbag

提示:

  • 1 <= s.length, t.length <= 1000
  • st 由英文字母组成

思路

  1. 状态表达

    • 选取第一个字符串 [0, i] 区间以及第二个字符串 [0, j] 区间作为研究对象,结合题目要求来定义状态表达。
    • 在这道题中,状态表达为 dp[i][j],表示在字符串 s[0, j] 区间内的所有子序列中,有多少个 t 字符串 [0, i] 区间内的子串。
  2. 状态转移方程

    • 根据最后一个位置的元素,结合题目要求进行分类讨论:

      • t[i] == s[j]
        

        时:

        • 选择 s[j] 作为结尾,相当于在状态 dp[i-1][j-1] 中的所有符合要求的子序列的后面,再加上一个字符 s[j],此时 dp[i][j] = dp[i-1][j-1]
        • 不选择 s[j] 作为结尾,相当于选择了状态 dp[i][j-1] 中所有符合要求的子序列,继承了上个状态里面的求得的子序列,此时 dp[i][j] = dp[i][j-1]
      • t[i] != s[j]
        

        时:

        • 子序列只能从 dp[i][j-1] 中选择所有符合要求的子序列,继承上个状态里面求得的子序列,此时 dp[i][j] = dp[i][j-1]
    • 综上,状态转移方程为:

      • 所有情况下都可以继承上一次的结果:dp[i][j] = dp[i][j-1]
      • t[i] == s[j] 时,可以多选择一种情况:dp[i][j] += dp[i-1][j-1]
  3. 初始化

    • 引入空串后,方便初始化,注意下标的映射关系以及确保后续填表是正确的。
    • s 为空时,t 的子串中有一个空串和它一样,因此初始化第一行全部为 1
  4. 填表顺序

    • 从上往下填每一行,每一行从左往右。
  5. 返回值

    • 根据状态表达,返回 dp[m][n] 的值。

代码

class Solution {
public:
    int numDistinct(string s, string t) {
        int m=t.size(),n=s.size();
        vector<vector<double>> dp(m+1,vector<double>(n+1));
        for(int j=0;j<=n;j++) dp[0][j]=1;

        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++)
            {
                dp[i][j]+=dp[i][j-1];
                if(t[i-1]==s[j-1]) dp[i][j]+=dp[i-1][j-1];
            }

        return dp[m][n];
    }
};

04.通配符匹配

题目链接:https://leetcode.cn/problems/wildcard-matching/

给你一个输入字符串 (s) 和一个字符模式 (p) ,请你实现一个支持 '?''*' 匹配规则的通配符匹配:

  • '?' 可以匹配任何单个字符。
  • '*' 可以匹配任意字符序列(包括空字符序列)。

判定匹配成功的充要条件是:字符模式必须能够 完全匹配 输入字符串(而不是部分匹配)。

示例 1:

输入:s = "aa", p = "a"
输出:false
解释:"a" 无法匹配 "aa" 整个字符串。

示例 2:

输入:s = "aa", p = "*"
输出:true
解释:'*' 可以匹配任意字符串。

示例 3:

输入:s = "cb", p = "?a"
输出:false
解释:'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

提示:

  • 0 <= s.length, p.length <= 2000
  • s 仅由小写英文字母组成
  • p 仅由小写英文字母、'?''*' 组成

思路

在处理两个字符串之间的动态规划问题时,通常按照以下步骤进行:

  1. 状态表达

    • 选取第一个字符串 [0, i] 区间以及第二个字符串 [0, j] 区间作为研究对象,结合题目的要求定义状态表达。
    • 在这道题中,我们定义状态表达为 dp[i][j],表示字符串 p[0, j] 区间内的子串能否匹配字符串 s[0, i] 区间内的子串。
  2. 状态转移方程

    • 根据最后一个位置的元素,结合题目要求,进行分类讨论:
      • s[i] == p[j]p[j] == '?' 时,两个字符串匹配上了当前的一个字符,只能从 dp[i-1][j-1] 中看当前字符前面的两个子串是否匹配,继承上个状态中的匹配结果,dp[i][j] = dp[i][j-1]
      • p[j] == '*' 时,匹配策略有两种选择:
        • 选择 '*' 匹配空字符串,相当于它匹配了一个寂寞,直接继承状态 dp[i][j-1]dp[i][j] = dp[i][j-1]
        • 选择 '*' 向前匹配 1 ~ n 个字符,直至匹配整个 s 串。相当于从 dp[k][j-1] (0 <= k <= i) 中所有匹配情况中,选择性继承可以成功的情况,dp[i][j] = dp[k][j-1] (0 <= k <= i)。
      • p[j] 不是特殊字符且不与 s[i] 相等时,无法匹配。综上,状态转移方程为:
        • s[i] == p[j]p[j] == '?' 时:dp[i][j] = dp[i-1][j-1]
        • p[j] == '*' 时,状态转移方程优化为:dp[i][j] = dp[i-1][j] || dp[i][j-1]
  3. 初始化

    • dp 数组的值表示是否匹配,初始化整个数组为 false
    • 由于需要用到前一行和前一列的状态,初始化第一行和第一列。
      • dp[0][0] 表示两个空串是否匹配,初始化为 true
      • 第一行表示 s 为空串,p 串与空串只有一种匹配可能,即 p 串表示为 "***",此时也相当于空串匹配上空串,将所有前导为 "*"p 子串与空串的 dp 值设为 true
      • 第一列表示 p 为空串,不可能匹配上 s 串,跟随数组初始化即可。
  4. 填表顺序

    • 从上往下填每一行,每一行从左往右。
  5. 返回值

    • 根据状态表达,返回 dp[m][n] 的值。

代码

class Solution {
public:
    bool isMatch(string s, string p) {
        int m=s.size(),n=p.size();
        s=" "+s,p=" "+p;
        vector<vector<bool>> dp(m+1,vector<bool>(n+1));
        dp[0][0]=true;
        for(int i=1;i<=n;i++)
            if(p[i]=='*') dp[0][i]=true;
            else break;

        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++)
            {
                if(p[j]=='*') dp[i][j]=dp[i][j-1]||dp[i-1][j];
                else dp[i][j]=(p[j]=='?'||s[i]==p[j])&&dp[i-1][j-1];
            }

        return dp[m][n];
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/430323.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

医院床旁交互系统概述 -智慧护理-全视通

全视通床旁交互系统是一种先进的医疗信息技术解决方案&#xff0c;旨在改善病患与医疗团队之间的沟通与交流。该系统通过集成多种高科技设备&#xff0c;为病患在病床边提供了一站式的信息交互平台&#xff0c;从而优化了医疗服务流程&#xff0c;提升了医疗体验。 首先&#x…

C++引入

引用不是新定义一个变量&#xff0c;而是给已经存在的变量取一个别名&#xff0c;编译器不会为了引用变量开辟内存空间&#xff0c;它和它引用的变量公用同一块内存空间。如李白被称为诗仙。李白和诗仙都是同一个人。 语法: 类型& 引用变量名(对象名)引用实体; 特性: 引用在…

coppeliasi4.0版本中使用循迹小车跟随路径时问题汇总

加入循迹小车&#xff0c;设置好路径后运行 发现报错&#xff0c;小车直线行驶不跟随设置好的路径移动 观察仿真中可知小车左右中传感器并不工作全是黑色&#xff0c;观察报错语句 Lua runtime error: [string "CUSTOMIZATION SCRIPT LeftSensor"]:12: Invalid hand…

基于SpringBoot的医护人员排班系统(代码+数据库+文档)

** &#x1f345;点赞收藏关注 → 私信领取本源代码、数据库&#x1f345; 本人在Java毕业设计领域有多年的经验&#xff0c;陆续会更新更多优质的Java实战项目 希望你能有所收获&#xff0c;少走一些弯路。&#x1f345;关注我不迷路&#x1f345;** 目录 一、研究背景 1.…

Vue 项目重复点击菜单刷新当前页面

需求&#xff1a;“在当前页面点击当前页面对应的菜单时&#xff0c;也能刷新页面。” 由于 Vue 项目的路由机制是路由不变的情况下&#xff0c;对应的组件是不重新渲染的。所以重复点击菜单不会改变路由&#xff0c;然后页面就无法刷新了。 方案一 在vue项目中&#xff0c;…

探索Python编程世界:从入门到精通

一.Python 从入门到精通 随着计算机科学的发展&#xff0c;编程已经成为了一种必备的技能。而 Python 作为一种简单易学、功能强大的编程语言&#xff0c;越来越受到人们的喜爱。本文将为初学者介绍 Python 编程的基础知识&#xff0c;帮助他们踏入 Python 编程的大门&#xf…

网络安全: Kali Linux 使用 MSF 渗透测试

目录 一、实验 1.环境 2.登录MSF&#xff08;Metasploit Framework&#xff09;控制台 3.MSF初始化 4.MSF 管理工作区 5.Kali Linux (2024.1) 对Windows server 进行网址目录扫描 6.Kali Linux (2022.4) 对Ubuntu进行网址目录扫描 7.Kali Linux (2024.1) 对Windows ser…

Java 的七种垃圾收集器

了解 Java 中的内存管理。 用 C 或 C 这样的编程语言写一个应用时&#xff0c;需要编写代码来销毁内存中不再需要的对象。当应用程序扩展得越来越复杂时&#xff0c;未使用对象被忽略释放的可能性就越大。这会导致内存泄露&#xff0c;最终内存耗尽&#xff0c;在某个时刻将没有…

Matlab/Simulink验证MAB建模规范

前言 为什么MAB&#xff1f; MathWorks Advisory Board&#xff08;MAB&#xff09;是由MathWorks公司设立的一个咨询委员会&#xff0c;旨在提供有关MathWorks产品和服务的反馈、建议和意见。MAB成员通常是来自学术界、工业界和其他领域的专业人士&#xff0c;他们在各自领域…

【Sql Server】C#通过拼接代码的方式组合添加sql语句,会出现那些情况,参数化的作用

欢迎来到《小5讲堂》&#xff0c;大家好&#xff0c;我是全栈小5。 这是《Sql Server》系列文章&#xff0c;每篇文章将以博主理解的角度展开讲解&#xff0c; 特别是针对知识点的概念进行叙说&#xff0c;大部分文章将会对这些概念进行实际例子验证&#xff0c;以此达到加深对…

【C++从0到王者】第四十七站:最小生成树

文章目录 一、最小生成树的概念1.概念2.最小生成树的构造方法 二、Kruskal算法1.算法思想2.代码实现 三、Prim算法1.算法思想2.代码实现3.试试所有节点为起始点 一、最小生成树的概念 1.概念 连通图&#xff1a;在无向图中&#xff0c;若从顶点v1到顶点v2有路径&#xff0c;则…

这本书太好了!150页就能让你上手大模型应用开发

如果问个问题&#xff1a;有哪些产品曾经创造了伟大的奇迹&#xff1f;ChatGPT 应该会当之无愧入选。 仅仅发布 5 天&#xff0c;ChatGPT 就吸引了 100 万用户——当然&#xff0c;数据不是关键&#xff0c;关键是其背后的技术开启了新的 AI 狂潮&#xff0c;成为技术变革的点火…

强势改进!基于改进多目标灰狼算法的冷热电联供型微电网运行优化程序代码!

适用平台&#xff1a;MatlabYalmipCplex 程序以综合能源系统/微电网为研究对象&#xff0c;将微电网的运行费用和环境污染成本作为优化目标&#xff0c;考虑冷热电负荷和设备运行要求的约束&#xff0c;建立的微电网的多目标优化模型&#xff0c;使用改进多目标灰狼算法算法进…

有个朋友被骗了,大家要擦亮眼睛

1.引言 大家好&#xff0c;我是Leo哥&#x1fae3;&#x1fae3;&#x1fae3;&#xff0c;昨天凌晨有个粉丝朋友找到Leo哥&#xff0c;咨询一些问题&#xff0c;现在的朋友们真卷呐&#xff0c;大半夜还在挑灯夜战。可无奈Leo哥12点之前已经睡了&#xff0c;身体为重&#xf…

智慧社区养老:Java与SpringBoot的技术融合

✍✍计算机毕业编程指导师 ⭐⭐个人介绍&#xff1a;自己非常喜欢研究技术问题&#xff01;专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目&#xff1a;有源码或者技术上的问题欢迎在评论区一起讨论交流&#xff01; ⚡⚡ Java、…

Day31|贪心算法1

贪心的本质是选择每一阶段的局部最优&#xff0c;从而达到全局最优。 无固定套路&#xff0c;举不出反例&#xff0c;就可以试试贪心。 一般解题步骤&#xff1a; 1.将问题分解成若干子问题 2.找出适合的贪心策略 3.求解每一个子问题的最优解 4.将局部最优解堆叠成全局最…

C语言第三十五弹---文件操作(上)

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】 文件操作 1、为什么使用文件&#xff1f; 2、什么是文件&#xff1f; 2.1、程序文件 2.2、数据文件 2.3、文件名 3、二进制文件和文本文件 4、文件的打开和…

YOLO v9训练自己数据集

原以为RT-DETR可以真的干翻YOLO家族&#xff0c;结果&#xff0c;&#xff01;&#xff01;&#xff01;&#xff01; 究竟能否让卷积神经网络重获新生&#xff1f; 1.数据准备 代码地址&#xff1a;https://github.com/WongKinYiu/yolov9 不能科学上网的评论区留言 数据集…

【Python】新手入门(2):避免将关键字作为标识符

Python新手入门&#xff08;2&#xff09;&#xff1a;避免将关键字作为标识符 &#x1f308; 个人主页&#xff1a;高斯小哥 &#x1f525; 高质量专栏&#xff1a;Matplotlib之旅&#xff1a;零基础精通数据可视化、Python基础【高质量合集】、PyTorch零基础入门教程&#x1…

蓝桥杯-单片机组基础7-存储器映射扩展与PWM脉冲调制(附小蜜蜂课程代码)

蓝桥杯单片机组备赛指南请查看这篇文章&#xff1a;戳此跳转蓝桥杯备赛指南文章 本文章针对蓝桥杯-单片机组比赛开发板所写&#xff0c;代码可直接在比赛开发板上使用。 型号&#xff1a;国信天长4T开发板&#xff08;绿板&#xff09;&#xff0c;芯片&#xff1a;IAP15F2K6…