算法沉淀——动态规划之两个数组的 dp（下）（leetcode真题剖析）

在这里插入图片描述

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

  • 01.正则表达式匹配
  • 02.交错字符串
  • 03.两个字符串的最小ASCII删除和
  • 04.最长重复子数组

01.正则表达式匹配

题目链接：https://leetcode.cn/problems/regular-expression-matching/

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

  • '.' 匹配任意单个字符
  • '*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

示例 1：

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

示例 2:

输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3：

输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

提示：

  • 1 <= s.length <= 20
  • 1 <= p.length <= 20
  • s 只包含从 a-z 的小写字母。
  • p 只包含从 a-z 的小写字母，以及字符 . 和 *。
  • 保证每次出现字符 * 时，前面都匹配到有效的字符

思路

在处理字符串匹配的动态规划问题时，通常按照以下步骤进行：

  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-1][j-1]。
      • 当 p[j] == '*' 时，匹配策略有两种选择：
        • 一种选择是：p[j-1]* 匹配空字符串，相当于这两个字符都匹配了一个寂寞，直接继承状态 dp[i][j-2]，dp[i][j] = dp[i][j-2]。
        • 另一种选择是：p[j-1]* 向前匹配 1 ~ n 个字符，直至匹配上整个 s 串。相当于从 dp[k][j-2] (0 < k <= i 且 s[k]~s[i] = p[j-1]) 中所有匹配情况中，选择性继承可以成功的情况，dp[i][j] = dp[k][j-2] (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][j-2] || dp[i-1][j]。

  3. 初始化：

    • dp 数组的值表示是否匹配，初始化整个数组为 false。
    • 由于需要用到前一行和前一列的状态，初始化第一行和第一列。
      • dp[0][0] 表示两个空串是否匹配，初始化为 true。
      • 第一行表示 s 为空串， 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=2;i<=n;i+=2)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-2]||(p[j-1]=='.'||p[j-1]==s[i])&&dp[i-1][j];else dp[i][j]=(p[j]==s[i]||p[j]=='.')&&dp[i-1][j-1];}return dp[m][n];}
};

02.交错字符串

题目链接：https://leetcode.cn/problems/interleaving-string/

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：

  • s = s1 + s2 + ... + sn
  • t = t1 + t2 + ... + tm
  • |n - m| <= 1
  • 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...

注意：a + b 意味着字符串 a 和 b 连接。

示例 1：

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出：true

示例 2：

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出：false

示例 3：

输入：s1 = "", s2 = "", s3 = ""
输出：true

提示：

  • 0 <= s1.length, s2.length <= 100
  • 0 <= s3.length <= 200
  • s1、s2、和 s3 都由小写英文字母组成

思路

  1. 状态表达：
    • 对于两个字符串的动态规划问题，首先考虑选取第一个字符串的 [0, i] 区间和第二个字符串的 [0, j] 区间作为研究对象。
    • 定义状态表达 dp[i][j]，表示字符串 s1 中 [1, i] 区间内的字符和字符串 s2 中 [1, j] 区间内的字符是否能够交错组成字符串 s3 中 [1, i + j] 区间内的字符。
  2. 状态转移方程：
    • 根据两个区间上的最后一个字符，进行分类讨论：
      • 如果 s3[i + j] = s1[i]，说明交错后的字符串的最后一个字符和 s1 的最后一个字符匹配了。这时，需要判断整个字符串是否能够交错组成，即 dp[i][j] = dp[i - 1][j]。
      • 如果 s3[i + j] = s2[j]，说明交错后的字符串的最后一个字符和 s2 的最后一个字符匹配了。这时，需要判断整个字符串是否能够交错组成，即 dp[i][j] = dp[i][j - 1]。
      • 如果两者的末尾字符都不等于 s3 最后一个位置的字符，说明不可能是两者的交错字符串，dp[i][j] 保持不变。
  3. 初始化：
    • 初始化第一个位置，dp[0][0] = true，因为空串与空串能够构成空串。
    • 初始化第一行，dp[0][j]，表示 s1 是空串，需要判断与 s2 的交错情况。如果 s2[j - 1] == s3[j - 1] 且 dp[0][j - 1] 为真，则 dp[0][j] = true。
    • 初始化第一列，dp[i][0]，表示 s2 是空串，需要判断与 s1 的交错情况。如果 s1[i - 1] == s3[i - 1] 且 dp[i - 1][0] 为真，则 dp[i][0] = true。
  4. 填表顺序：
    • 从上往下逐行填表，每一行从左往右。
  5. 返回值：
    • 根据状态表达 dp[m][n] 的值，其中 m 和 n 分别是 s1 和 s2 的长度，判断是否能够交错组成字符串 s3。

代码

class Solution {
public:bool isInterleave(string s1, string s2, string s3) {int m=s1.size(),n=s2.size();if(s3.size()!=m+n) return false;s1=" "+s1,s2=" "+s2,s3=" "+s3;vector<vector<bool>> dp(m+1,vector<bool>(n+1));dp[0][0]=true;for(int i=1;i<=n;++i) if(s2[i]==s3[i]) dp[0][i] = true;else break;for(int i=1;i<=m;++i)if(s1[i]==s3[i]) dp[i][0] = true;else break;for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)dp[i][j]=(s1[i]==s3[i+j]&&dp[i-1][j])||(s2[j]==s3[i+j]&&dp[i][j-1]);return dp[m][n];}
};

03.两个字符串的最小ASCII删除和

题目链接：https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/

给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。

示例 1:

输入: s1 = "sea", s2 = "eat"
输出: 231
解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。
在 "eat" 中删除 "t" 并将 116 加入总和。
结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。

示例 2:

输入: s1 = "delete", s2 = "leet"
输出: 403
解释: 在 "delete" 中删除 "dee" 字符串变成 "let"，
将 100[d]+101[e]+101[e] 加入总和。在 "leet" 中删除 "e" 将 101[e] 加入总和。
结束时，两个字符串都等于 "let"，结果即为 100+101+101+101 = 403 。
如果改为将两个字符串转换为 "lee" 或 "eet"，我们会得到 433 或 417 的结果，比答案更大。

提示:

  • 0 <= s1.length, s2.length <= 1000
  • s1 和 s2 由小写英文字母组成

思路

  1. 状态表达：

    • dp[i][j] 表示字符串 s1 的 [0, i] 区间以及字符串 s2 的 [0, j] 区间内的所有的子序列中，公共子序列的 ASCII 最大和。

  2. 状态转移方程：

    • 根据最后一个位置的元素，进行情况讨论：

      • 如果 s1[i] == s2[j]，说明当前字符可以被加入到公共子序列中，此时 dp[i][j] = dp[i - 1][j - 1] + s1[i]。

      • 如果

        s1[i] != s2[j]

        ，此时有三种可能：

        • 在 s1 的 [0, i - 1] 区间以及 s2 的 [0, j] 区间内找公共子序列的最大和，即 dp[i][j] = dp[i - 1][j]。
        • 在 s1 的 [0, i] 区间以及 s2 的 [0, j - 1] 区间内找公共子序列的最大和，即 dp[i][j] = dp[i][j - 1]。
        • 在 s1 的 [0, i - 1] 区间以及 s2 的 [0, j - 1] 区间内找公共子序列的最大和，即 dp[i][j] = dp[i - 1][j - 1]。

      • 由于前两种情况包含了第三种情况，因此只需考虑前两种情况下的最大值。

  3. 初始化：

    • 引入空串后，扩大了状态表的规模，方便初始化。
    • 需要注意下标的映射关系以及确保后续填表的正确性。
    • 当 s1 和 s2 为空时，没有长度，所以第一行和第一列的值初始化为 0。

  4. 填表顺序：

    • 从上往下逐行填表，每一行从左往右。

  5. 返回值：

    • 先找到 dp[m][n]，即最大公共 ASCII 和。
    • 统计两个字符串的 ASCII 码和 sum。
    • 返回 sum - 2 * dp[m][n]。

代码

class Solution {
public:int minimumDeleteSum(string s1, string s2) {int m=s1.size(),n=s2.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++){dp[i][j]=max(dp[i][j-1],dp[i-1][j]);if(s1[i-1]==s2[j-1]) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+s1[i-1]);}int sum=0;for(auto s:s1) sum+=s;for(auto s:s2) sum+=s;return sum-dp[m][n]*2;}
};

04.最长重复子数组

题目链接：https://leetcode.cn/problems/maximum-length-of-repeated-subarray/

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

示例 1：

输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。

示例 2：

输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5

提示：

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 100

思路

  1. 状态表达：
    • dp[i][j] 表示以第一个数组的第 i 位置为结尾以及第二个数组的第 j 位置为结尾时，两个数组的最长重复子数组的长度。
  2. 状态转移方程：
    • 当 nums1[i] == nums2[j] 时，说明当前位置两个数组的元素相等，此时最长重复子数组的长度应该等于 1 加上除去最后一个位置时，以 i - 1, j - 1 为结尾的最长重复子数组的长度，即 dp[i][j] = 1 + dp[i - 1][j - 1]。
  3. 初始化：
    • 为了处理越界的情况，添加了一行和一列，使 dp 数组的下标从 1 开始。
    • 第一行表示第一个数组为空，因此没有重复子数组，所以其中的值设置为 0。
    • 第一列同理。
  4. 填表顺序：
    • 根据状态转移方程，从上往下逐行填表，每一行从左往右。
  5. 返回值：
    • 根据状态表达，需要返回 dp 表中的最大值。

代码

class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {int m=nums1.size(),n=nums2.size();vector<vector<int>> dp(m+1,vector<int>(n+1));int ret=0;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, ret=max(ret,dp[i][j]);return ret;}
};

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

【Unity每日一记】角色控制器Character Contorller

【Unity每日一记】角色控制器Character Contorller

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;元宇宙-秩沅 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 秩沅 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a;Uni…
阅读更多...
Python中的数据类型

Python中的数据类型

如果说python中的数据类型,那我们要从标准数据类型说起,在python中标准数据类型如下: 数字类型: 数字数据类型用于存储数值。 他们是不可改变的数据类型&#xff0c;这意味着改变数字数据类型会分配一个新的对象。 在python2.X中数据类型分的比较多,有int(有符号整型),long(…
阅读更多...
Redis——服务器

Redis——服务器

Redis服务器负责与多个客户端建立网络连接&#xff0c;处理客户端发送的命令请求&#xff0c;在数据库中保存客户端执行命令所产生的数据&#xff0c;并通过资源管理来维持服务器自身的运行。 一. 命令请求的执行过程 一个命令请求从发送到获得回复过程中&#xff0c;客户端和服…
阅读更多...
【MySQL】基本查询（表的增删改查）-- 详解

【MySQL】基本查询（表的增删改查）-- 详解

CRUD&#xff1a;Create&#xff08;创建&#xff09;&#xff0c;Retrieve&#xff08;读取&#xff09;&#xff0c;Update&#xff08;更新&#xff09;&#xff0c;Delete&#xff08;删除&#xff09;。 一、Create insert [into] table_name [(column [, column] ...)] v…
阅读更多...
从0到1实现五子棋游戏！！

从0到1实现五子棋游戏！！

Hello&#xff0c;好久不见宝子们&#xff0c;今天来给大家更一个五子棋的程序~ 我们今天要讲的内容如下&#xff1a; 文章目录 1.五子棋游戏介绍1.1 游戏玩法介绍&#xff1a; 2.准备工作2.1 具体操作流程 3.游戏程序主函数4.初始化棋盘4.1.定义宏变量4.2 初始化棋盘 5.打印…
阅读更多...
什么是VR紧急情况模拟|消防应急虚拟展馆|VR游戏体验馆加盟

什么是VR紧急情况模拟|消防应急虚拟展馆|VR游戏体验馆加盟

VR紧急情况模拟是利用虚拟现实&#xff08;Virtual Reality&#xff0c;简称VR&#xff09;技术来模拟各种紧急情况和应急场景的训练和演练。通过VR技术&#xff0c;用户可以身临其境地体验各种紧急情况&#xff0c;如火灾、地震、交通事故等&#xff0c;以及应对这些紧急情况的…
阅读更多...
常用git 打tag命令

常用git 打tag命令

1.查看所有tag git tag 2.创建 v5.0.0的tag git tag v5.0.0 git tag &#xff08;创建后查看&#xff09; 3.推送到远程tag git push origin v5.0.0 4.删除远程tag git push origin --delete v5.0.0 5.删除本地tag git tag -d v5.0.0 6.添加带有备注信息的tag git tag v5.…
阅读更多...
linux系统Jenkins的安装

linux系统Jenkins的安装

Jenkins安装 安装上传安装包解压包首次登录要去服务器查看密码&#xff0c;更改密码选择需要安装的插件设置Admin用户和密码安装完成 安装 上传安装包 上传 jdk17 tomcat jenkins.war的安装包 . 上传 tomcat安装包解压包 解压jdk tar xf jdk-11.0.18_linux-x64_bin.tar.gz解…
阅读更多...
Golang embed 库全面解析：从基础到高级应用

Golang embed 库全面解析：从基础到高级应用

Golang embed 库全面解析&#xff1a;从基础到高级应用 引言Golang的 embed&#xff1a;简化资源管理提升可移植性与便利性适用场景的拓展 embed 库的基本概念embed 库的工作原理使用 embed 的基本语法访问嵌入资源的方法embed 的限制 如何使用 embed嵌入单个文件嵌入整个目录结…
阅读更多...
python 3.11中安装sympy(符号工具包)

python 3.11中安装sympy(符号工具包)

1.python环境&#xff1a; 2.安装遇到问题&#xff1a; 其中一台Win10系统上&#xff1a; … 另一台Win10系统上&#xff1a; 3.升级pip cmd命令行中&#xff0c;执行如下命令&#xff1a; python.exe -m pip installl --upgrade pip 4.再次安装sympy cmd命令行中&…
阅读更多...
前端架构: 脚手架包管理工具之lerna的全流程开发教程

前端架构: 脚手架包管理工具之lerna的全流程开发教程

Lerna 1 &#xff09;文档 Lerna 文档 https://www.npmjs.com/package/lernahttps://lerna.js.org [请直达这个链接] 使用 Lerna 帮助我们做包管理&#xff0c;并不复杂&#xff0c;中间常用的命令并不是很多这里是命令直达&#xff1a;https://lerna.js.org/docs/api-referen…
阅读更多...
深度学习--神经网络基础

深度学习--神经网络基础

神经网络 人工神经网络&#xff08; Artificial Neural Network &#xff0c; 简写为 ANN &#xff09;也简称为神经网络&#xff08; NN &#xff09;&#xff0c;是一种模仿生物神经网络结构和 功能的计算模型 。人脑可以看做是一个生物神经网络&#xff0c;由众多的 神经元…
阅读更多...
刷题第2天（中等题）：LeetCode59--螺旋矩阵--考察模拟能力（边界条件处理）

刷题第2天（中等题）：LeetCode59--螺旋矩阵--考察模拟能力（边界条件处理）

LeetCode59: 给你一个正整数 n &#xff0c;生成一个包含 1 到 n2 所有元素&#xff0c;且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。 示例 1&#xff1a; 输入&#xff1a;n 3 输出&#xff1a;[[1,2,3],[8,9,4],[7,6,5]]示例 2&#xff1a; 输入&#xff1a…
阅读更多...
高刷显示器 - HKC VG253KM

高刷显示器 - HKC VG253KM

&#x1f525;&#x1f525; 今天来给大家揭秘一款电竞神器 - HKC VG253KM 高刷电竞显示器&#xff01;这款显示器可是有着雄鹰展翅般的设计灵感&#xff0c;背后的大鹏展翅鹰翼图腾让人过目难忘。那么&#xff0c;这款显示器到底有哪些过人之处呢&#xff1f;一起来看看吧&…
阅读更多...
Automated Testing for LLMOps 01：使用CircleCI进行持续集成CI

Automated Testing for LLMOps 01：使用CircleCI进行持续集成CI

Automated Testing for LLMOps 这是学习https://www.deeplearning.ai/short-courses/automated-testing-llmops/ 这门课的笔记 Learn how LLM-based testing differs from traditional software testing and implement rules-based testing to assess your LLM application. …
阅读更多...
2024年腾讯云4核8G12M配置的轻量服务器同时支持多大访问量?

2024年腾讯云4核8G12M配置的轻量服务器同时支持多大访问量?

腾讯云4核8G服务器支持多少人在线访问&#xff1f;支持25人同时访问。实际上程序效率不同支持人数在线人数不同&#xff0c;公网带宽也是影响4核8G服务器并发数的一大因素&#xff0c;假设公网带宽太小&#xff0c;流量直接卡在入口&#xff0c;4核8G配置的CPU内存也会造成计算…
阅读更多...
深入理解网络通信基本原理和tcp/ip协议

深入理解网络通信基本原理和tcp/ip协议

深入理解网络通信基本原理和tcp/ip协议 一、计算机网络体系1&#xff0c;计算机网络体系结构2&#xff0c;网络中数据传输2.1&#xff0c;浏览器中输入一个url的执行流程2.2&#xff0c;数据在网络中是的传输流程 3&#xff0c;三次握手和四次挥手3.1&#xff0c;三次握手3.1.1…
阅读更多...
推荐一款桌面端redis连接工具, redis desktop manager替代品——another redis desktop manager

推荐一款桌面端redis连接工具, redis desktop manager替代品——another redis desktop manager

下载地址 Another Redis Desktop Manager | 更快、更好、更稳定的Redis桌面(GUI)管理客户端&#xff0c;兼容Windows、Mac、Linux&#xff0c;性能出众&#xff0c;轻松加载海量键值 封面对比 对比redis desktop manager &#xff0c;ui上有巨大的改进 但是redis desktop ma…
阅读更多...
【基于Ubuntu20.04的Autoware.universe安装过程】方案一：虚拟机 | 详细记录 | Vmware | 全过程图文 by.Akaxi

【基于Ubuntu20.04的Autoware.universe安装过程】方案一：虚拟机 | 详细记录 | Vmware | 全过程图文 by.Akaxi

目录 一、Autoware.universe背景 二、虚拟机配置 三、Ubuntu20.04安装 四、GPU显卡安装 五、ROS2-Galactic安装 六、ROS2-dev-tools安装 七、rmw-implementation安装 八、pacmod安装 九、autoware-core安装 十、autoware universe dependencies安装 十一、安装pre-c…
阅读更多...
如何使用固定公网地址远程访问本地RStudio Server【内网穿透】

如何使用固定公网地址远程访问本地RStudio Server【内网穿透】

文章目录 前言1. 安装RStudio Server2. 本地访问3. Linux 安装cpolar4. 配置RStudio server公网访问地址5. 公网远程访问RStudio6. 固定RStudio公网地址 前言 RStudio Server 使你能够在 Linux 服务器上运行你所熟悉和喜爱的 RStudio IDE&#xff0c;并通过 Web 浏览器进行访问…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023