【算法篇】逐步理解动态规划模型7（两个数组dp问题）

目录

两个数组dp问题

1.最长公共子序列

2.不同的子序列

3.通配符匹配

        本文旨在通过对力扣上三道题进行讲解来让大家对使用动态规划解决两个数组的dp问题有一定思路，培养大家对状态定义，以及状态方程书写的思维。

顺序：

题目链接-》算法思路-》代码呈现

两个数组dp问题

动态规划类题目解题步骤：

  1. 依据题目进行状态表示(dp[i]的含义)
  2. 写出状态转移方程(类似于dp[i]=dp[i-1]+dp[i-2])
  3. 为防止填表时数组越界，对dp表进行初始化（dp[0]=dp[1]=1）
  4. 搞清楚填表顺序（从前往后或者从后往前）
  5. 利用dp表返回问题答案

1.最长公共子序列

题目链接：

https://leetcode.cn/problems/longest-common-subsequence/

算法思路：

1. 状态表⽰：
        对于两个数组的动态规划，我们的定义状态表⽰的经验就是：
  1. 选取第⼀个数组 [0, i] 区间以及第⼆个数组 [0, j] 区间作为研究对象；
  2. 结合题⽬要求，定义状态表⽰。
在这道题中，我们根据定义状态表⽰为：
dp[i][j] 表⽰： s1 的 [0, i] 区间以及 s2 的 [0, j] 区间内的所有的⼦序列中，最⻓公共⼦序列的⻓度。
2. 状态转移⽅程：
        分析状态转移⽅程的经验就是根据「最后⼀个位置」的状况，分情况讨论。
对于 dp[i][j] ，我们可以根据 s1[i] 与 s2[j] 的字符分情况讨论：
1.  两个字符相同， s1[i] = s2[j] ：那么最⻓公共⼦序列就在 s1 的 [0, i - 1] 及 s2 的 [0, j - 1] 区间上找到⼀个最⻓的，然后再加上 s1[i] 即可。因此dp[i][j] = dp[i - 1][j - 1] + 1 ；
2. 两个字符不相同， s1[i] != s2[j] ：那么最⻓公共⼦序列⼀定不会同时以 s1[i]和 s2[j] 结尾。那么我们找最⻓公共⼦序列时，有下⾯三种策略：
  • 去 s1 的 [0, i - 1] 以及 s2 的 [0, j] 区间内找：此时最⼤⻓度为 dp[i - 1][j] ；
  • 去 s1 的 [0, i] 以及 s2 的 [0, j - 1] 区间内找：此时最⼤⻓度为 dp[i ] [j - 1] ；
  • 去 s1 的 [0, i - 1] 以及 s2 的 [0, j - 1] 区间内找：此时最⼤⻓度为dp[i - 1][j - 1] 。
我们要三者的最⼤值即可。但是我们细细观察会发现，第三种包含在第⼀种和第⼆种情况⾥⾯，但是我们求的是最⼤值，并不影响最终结果。因此只需求前两种情况下的最⼤值即可。
综上，状态转移⽅程为：
if(s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1] + 1 ;
if(s1[i] != s2[j]) dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) 。
3. 初始化：
  1. 「空串」是有研究意义的，因此我们将原始 dp 表的规模多加上⼀⾏和⼀列，表⽰空串。
  2. 引⼊空串后，⼤⼤的⽅便我们的初始化。
  3. 但也要注意「下标的映射关系」，以及⾥⾯的值要「保证后续填表是正确的」。
当 s1 为空时，没有⻓度，同理 s2 也是。因此第⼀⾏和第⼀列⾥⾯的值初始化为 0 即可保证后续填表是正确的。
4. 填表顺序：
        根据「状态转移⽅程」得：从上往下填写每⼀⾏，每⼀⾏从左往右。
5. 返回值：
        根据「状态表⽰」得：返回 dp[m][n] 。

代码呈现：

class Solution {public int longestCommonSubsequence(String text1, String text2) {int re=0;char[] s=text1.toCharArray();char[] s1=text2.toCharArray();int m=s.length,n=s1.length;int[][] dp=new int[m+1][n+1];for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(s[i-1]==s1[j-1]){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);}}}return dp[m][n];}
}

2.不同的子序列

题目链接：

https://leetcode.cn/problems/distinct-subsequences/

算法思路：

1. 状态表⽰：
        对于两个字符串之间的 dp 问题，我们⼀般的思考⽅式如下：
  1. 选取第⼀个字符串的 [0, i] 区间以及第⼆个字符串的 [0, j] 区间当成研究对象，结合题⽬的要求来定义「状态表⽰」；
  2. 然后根据两个区间上「最后⼀个位置的字符」，来进⾏「分类讨论」，从⽽确定「状态转移⽅程」。
我们可以根据上⾯的策略，解决⼤部分关于两个字符串之间的 dp 问题。
dp[i][j] 表⽰：在字符串 s 的 [0, j] 区间内的所有⼦序列中，有多少个 t 字符串 [0,i] 区间内的⼦串。
2. 状态转移⽅程：
        ⽼规矩，根据「最后⼀个位置」的元素，结合题⽬要求，分情况讨论：
1. 当 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] 时的结果。
2. 当 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. 初始化：
  1. 「空串」是有研究意义的，因此我们将原始 dp 表的规模多加上⼀⾏和⼀列，表⽰空串。
  2. 引⼊空串后，⼤⼤的⽅便我们的初始化。
  3. 但也要注意「下标的映射关系」，以及⾥⾯的值要「保证后续填表是正确的」。
当 s 为空时， t 的⼦串中有⼀个空串和它⼀样，因此初始化第⼀⾏全部为 1 。
4. 填表顺序：
        「从上往下」填每⼀⾏，每⼀⾏「从左往右」。
5. 返回值：
        根据「状态表⽰」，返回 dp[m][n] 的值。
本题有⼀个巨恶⼼的地⽅，题⽬上说结果不会超过 int 的最⼤值，但是实际在计算过程会会超。为
了避免报错，我们选择 double 存储结果。

代码呈现：

class Solution {public int numDistinct(String s, String t) {int MOD=1000000007;s=" "+s;t=" "+t;char[] s1=s.toCharArray();char[] s2=t.toCharArray();int n=s1.length;int m=s2.length;int[][] dp=new int[n][m];for(int i=0;i<n;i++){dp[i][0]=1;}for(int i=1;i<n;i++){for(int j=1;j<m;j++){dp[i][j]=dp[i-1][j];if(s1[i]==s2[j]){dp[i][j]+=dp[i-1][j-1];}}}return dp[n-1][m-1];}
}

3.通配符匹配

题目链接：

https://leetcode.cn/problems/wildcard-matching/

算法思路：

1. 状态表⽰：
        对于两个字符串之间的 dp 问题，我们⼀般的思考⽅式如下：
  1. 选取第⼀个字符串的 [0, i] 区间以及第⼆个字符串的 [0, j] 区间当成研究对象，结合题⽬的要求来定义「状态表⽰」；
  2. 然后根据两个区间上「最后⼀个位置的字符」，来进⾏「分类讨论」，从⽽确定「状态转移⽅程」。
我们可以根据上⾯的策略，解决⼤部分关于两个字符串之间的 dp 问题。
因此，我们定义状态表⽰为：dp[i][j] 表⽰： p 字符串 [0, j] 区间内的⼦串能否匹配字符串 s 的 [0, i] 区间内的⼦串。
2. 状态转移⽅程：
        ⽼规矩，根据最后⼀个位置的元素，结合题⽬要求，分情况讨论：
1. 当 s[i] == p[j] 或 p[j] == '?' 的时候，此时两个字符串匹配上了当前的⼀个字符，只能从 dp[i - 1][j - 1] 中看当前字符前⾯的两个⼦串是否匹配。只能继承上个状态中的匹配结果， dp[i][j] = dp[i][j - 1] ；
2. 当 p[j] == '*' 的时候，此时匹配策略有两种选择：
  • ⼀种选择是： * 匹配空字符串，此时相当于它匹配了⼀个寂寞，直接继承状态 dp[i][j - 1] ，此时 dp[i][j] = dp[i][j - 1] ；
  • 另⼀种选择是： * 向前匹配 1 ~ n 个字符，直⾄匹配上整个 s1 串。此时相当于从 dp[k][j - 1] (0 <= k <= i) 中所有匹配情况中，选择性继承可以成功的情况。此时 dp[i][j] = dp[k][j - 1] (0 <= k <= i) ；
3. 当  p[j] 不是特殊字符，且不与 s[i] 相等时，⽆法匹配。三种情况加起来，就是所有可能的匹配结果。
综上所述，状态转移⽅程为：
  • 当 s[i] == p[j] 或 p[j] == '?' 时： dp[i][j] = dp[i][j - 1] ；
  • 当 p[j] == '*' 时，有多种情况需要讨论： dp[i][j] = dp[k][j - 1] (0 <=k <= i) ；
优化：当我们发现，计算⼀个状态的时候，需要⼀个循环才能搞定的时候，我们要想到去优化。优
化的⽅向就是⽤⼀个或者两个状态来表⽰这⼀堆的状态。通常就是把它写下来，然后⽤数学的⽅式
做⼀下等价替换：
当 p[j] == '*' 时，状态转移⽅程为：
dp[i][j] = dp[i][j - 1] || dp[i - 1][j - 1] || dp[i - 2][j - 1]
......
我们发现 i 是有规律的减⼩的，因此我们去看看 dp[i - 1][j] ：
dp[i - 1][j] = dp[i - 1][j - 1] || dp[i - 2][j - 1] || dp[i - 3][j - 1] ...... 我们惊奇的发现， dp[i][j] 的状态转移⽅程⾥⾯除了第⼀项以外，其余的都可以⽤ dp[i - 1][j] 替代。因此，我们优化我们的状态转移⽅程为： dp[i][j] = dp[i - 1][j] || dp[i][j - 1] 。
3. 初始化：
        由于 dp 数组的值设置为是否匹配，为了不与答案值混淆，我们需要将整个数组初始化为false 。
由于需要⽤到前⼀⾏和前⼀列的状态，我们初始化第⼀⾏、第⼀列即可。
  • dp[0][0] 表⽰两个空串能否匹配，答案是显然的， 初始化为 true 。
  • 第⼀⾏表⽰ s 是⼀个空串， p 串和空串只有⼀种匹配可能，即 p 串表⽰为 "***" ，此时 也相当于空串匹配上空串。所以，我们可以遍历 p 串，把所有前导为 "*" 的 p ⼦串和空串 的 dp 值设为 true 。
  • 第⼀列表⽰ p 是⼀个空串，不可能匹配上 s 串，跟随数组初始化即可。
4. 填表顺序：
        从上往下填每⼀⾏，每⼀⾏从左往右。
5. 返回值：
        根据状态表⽰，返回 dp[m][n] 的值。

代码呈现：

class Solution {public boolean isMatch(String s, String p) {s=" "+s;p=" "+p; char[] s1=s.toCharArray();char[] s2=p.toCharArray();int n=s1.length;int m=s2.length;boolean[][] dp=new boolean[n][m];dp[0][0]=true;for(int i=1;i<m;i++){if(s2[i]=='*'){dp[0][i]=dp[0][i-1];}}for(int i=1;i<n;i++){for(int j=1;j<m;j++){if(s2[j]=='?'||s1[i]==s2[j]){dp[i][j]=dp[i-1][j-1];}if(s2[j]=='*'){dp[i][j]=dp[i][j-1]||dp[i-1][j];}}}return dp[n-1][m-1];}
}

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

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

相关文章

什么是 HTTP Range 请求（范围请求）

什么是 HTTP Range 请求（范围请求）

HTTP Range 请求&#xff0c;即范围请求&#xff0c;是一种 HTTP 请求方法&#xff0c;允许客户端请求资源的部分数据。这种请求在处理大型文件&#xff08;如视频、音频、或大文件下载&#xff09;时特别有用&#xff0c;因为它可以有效地进行断点续传和按需加载数据&#xff…
阅读更多...
java集合（十） ---- LinkedList 类

java集合（十） ---- LinkedList 类

目录 十、LinkedList 类 10.1 位置 10.2 特点 10.3 与 ArrayList 的区别 10.4 构造方法 10.5 常用方法 十、LinkedList 类 10.1 位置 LinkedList 类位于 java.util 包下 10.2 特点 是 List 接口的实现类是 Deque 接口的实现类底层使用双向循环链表结构 10.3 与 Arra…
阅读更多...
kafka消费的模式及消息积压处理方案

kafka消费的模式及消息积压处理方案

目录 1、kafka消费的流程 2、kafka的消费模式 2.1、点对点模式 2.2、发布-订阅模式 3、consumer消息积压 3.1、处理方案 3.2、积压量 4、消息过期失效 5、kafka注意事项 Kafka消费积压(Consumer Lag)是指消费者处理消息的速度跟不上生产者发送消息的速度&#xff0c;导致消息在…
阅读更多...
RAG实践：Routing机制与Query Construction策略

RAG实践：Routing机制与Query Construction策略

Routing机制与Query Construction策略 前言RoutingLogical RoutingChatOpenAIStructuredRouting DatasourceConclusion Semantic RoutingEmbedding & LLMPromptRounting PromptConclusion Query ConstructionGrab Youtube video informationStructuredPrompt GithubReferen…
阅读更多...
基于python的web系统界面登录

基于python的web系统界面登录

#让我们的电脑可以支持服务访问 #需要一个web框架 #pip install Flask from flask import Flask, render_template,request from random import randint app Flask(__name__) app.route(/index) def index():uname request.args.get("uname")return f"主页&am…
阅读更多...
MATLAB Simulink 终极入门指南：从零设计智能控制系统

MATLAB Simulink 终极入门指南：从零设计智能控制系统

为什么工程师都爱Simulink？ 想象一下：不写一行代码就能设计机器人控制器、飞行算法甚至核反应堆！ MATLAB Simulink正是这样的可视化神器。全球70%的汽车ECU、航天器控制系统用它开发。本文将带你从零设计一个智能温控系统，融入创新性的模糊PID控制，并生成可部署的C代码！…
阅读更多...
vue3 javascript 复杂数值计算操作技巧

vue3 javascript 复杂数值计算操作技巧

在Vue 3中处理复杂数值计算&#xff0c;你可以采用多种策略来确保代码的可读性、可维护性和性能。以下是一些实用的技巧和最佳实践&#xff1a; 1. 使用计算属性&#xff08;Computed Properties&#xff09; Vue 3的computed属性非常适合处理复杂的数值计算。它们是基于响应…
阅读更多...
26.【.NET8 实战--孢子记账--从单体到微服务--转向微服务】--单体转微服务--角色权限管理

26.【.NET8 实战--孢子记账--从单体到微服务--转向微服务】--单体转微服务--角色权限管理

在现代企业级应用中&#xff0c;角色权限管理是保障系统安全和提升用户体验的核心基础功能。一个高效的角色权限系统不仅能够有效防止越权访问&#xff0c;还能简化系统的维护和扩展。本文将系统性介绍角色权限管理的核心实现思路&#xff0c;包括架构设计、性能优化、安全机制…
阅读更多...
[VSCode] VSCode 设置 python 的编译器

[VSCode] VSCode 设置 python 的编译器

VSCode 设置 python 的编译器 快捷键&#xff1a;CTRL SHIFT P 弹出 VSCode 的命令框输入 Python : select Interpretor选择自己需要的 python 环境&#xff1b;如 python 3.8 或者 python 3.10 版本
阅读更多...
基于PEMFC质子交换膜燃料电池系统的simulink建模与仿真

基于PEMFC质子交换膜燃料电池系统的simulink建模与仿真

目录 1.课题概述 2.系统仿真结果 3.核心程序 4.系统仿真参数 5.系统原理简介 6.参考文献 7.完整工程文件 1.课题概述 本课题是一个燃料电池&#xff08;大概率是质子交换膜燃料电池&#xff0c;PEMFC &#xff09;的数学模型仿真框图&#xff0c;用于模拟燃料电池的电特…
阅读更多...
git-build-package 工具代码详细解读

git-build-package 工具代码详细解读

git-build-package&#xff08;gbp&#xff09;是一个用于从 Git 仓库管理 Debian 软件包的工具&#xff0c;其代码架构和实现原理体现了对 Git 版本控制系统和 Debian 打包流程的深度整合。以下是对其代码的详细解读&#xff1a; 代码架构设计 gbp 的代码架构设计围绕其核心…
阅读更多...
如何使用ChatGPT快速完成一篇论文初稿？

如何使用ChatGPT快速完成一篇论文初稿？

2小时写完论文初稿&#xff0c;学境思源&#xff0c;听起来是不是有点不真实&#xff1f;一键生成论文初稿&#xff01;但如果你有一个清晰的框架、良好的写作节奏&#xff0c;acaids.com。再配合像ChatGPT这样的写作助手——真的可以做到。 这篇文章就是手把手告诉你&#xf…
阅读更多...
Docker PowerJob

Docker PowerJob

1. Docker PowerJob 1. 拉取PowerJob服务端镜像 docker pull tjqq/powerjob-server:4.3.92. 创建数据卷目录用于持久化数据 mkdir -p /home/docker/powerjob/logs mkdir -p /home/docker/powerjob/data mkdir -p /home/docker/powerjob/server mkdir -p /home/docker/powerjob…
阅读更多...
Python数据可视化：NumPy生成与Matplotlib折线图绘制

Python数据可视化：NumPy生成与Matplotlib折线图绘制

一、数据生成与可视化概述 在数据分析和科学计算领域，Python已成为最受欢迎的编程语言之一。这主要得益于其丰富的数据处理库和强大的可视化工具。数据可视化是将抽象数据转化为直观图形表示的过程，它能够帮助我们发现数据中的模式、趋势和异常值，从而做出更明智的决策。 …
阅读更多...
26.多表查询

26.多表查询

1.笛卡尔集 创建俩表&#xff1a; -- 创建部门表&#xff08;dept&#xff09; use mysql_learn CREATE TABLE dept (deptno INT PRIMARY KEY, dname VARCHAR(50) NOT NULL, loc VARCHAR(50) );-- 创建员工表&#xff08;emp&#xff09; CREATE TABLE emp (em…
阅读更多...
深度学习题目（仅供参考）

深度学习题目（仅供参考）

一、注意力和transformer 一、选择题 注意力机制的核心步骤不包括&#xff1f; A. 计算注意力分布 B. 加权平均输入信息 C. 随机丢弃部分输入 D. 打分函数计算相关性 答案&#xff1a;C&#xff08;硬性注意力虽随机选择输入&#xff0c;但核心步骤仍为分布计算与加权&#xf…
阅读更多...
WebWorker：提升前端性能的多线程利器

WebWorker：提升前端性能的多线程利器

简介 在现代Web开发中&#xff0c;随着应用越来越复杂&#xff0c;JavaScript的单线程模型开始显现其局限性。Web Workers的出现为解决这一问题提供了优雅的方案&#xff0c;它允许开发者在后台线程中运行脚本&#xff0c;而不会影响主线程的性能。 Web Workers是HTML5标准的…
阅读更多...
milvus教程：collection和scheme

milvus教程：collection和scheme

环境配置&#xff1a;可以看上一节 一.数据库使用 连接 Milvus Standalone创建数据库 my_database_1&#xff08;无额外属性&#xff09;创建数据库 my_database_2&#xff08;设置副本数为 3&#xff09;列出所有数据库查看默认数据库&#xff08;default&#xff09;详情修…
阅读更多...
14：00开始面试，14：06就出来了，问的问题有点变态。。。

14：00开始面试，14：06就出来了，问的问题有点变态。。。

从小厂出来&#xff0c;没想到在另一家公司又寄了。 到这家公司开始上班&#xff0c;加班是每天必不可少的&#xff0c;看在钱给的比较多的份上&#xff0c;就不太计较了。没想到6月一纸通知&#xff0c;所有人不准加班&#xff0c;加班费不仅没有了&#xff0c;薪资还要降40%…
阅读更多...
Electron（01）

Electron（01）

Electron Electron是什么 electron可以使用前端技术开发桌面应用&#xff0c;跨平台性&#xff0c;开发一套应用&#xff0c;可以打包到三个平台。 electron结合Chromium&#xff08;谷歌内核&#xff09;和 Node.js 和Native Api 当使用 Electron 时&#xff0c;很重要的一…
阅读更多...
最新文章

Copyright @ 2022~2023