算法系列--两个数组的dp问题(1)

💕"低头要有勇气，抬头要有底气。"💕
作者：Mylvzi
文章主要内容：算法系列–两个数组的dp问题(1)
在这里插入图片描述

大家好,今天为大家带来的是算法系列--两个数组的dp问题(1),两个数组的dp问题在动态规划问题中属于较难的部分,状态转移方程不易推导,希望大家通过下面的几道题目能够掌握

1.最长公共子序列

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

分析:
题目要找的是两个字符串中,公共子序列的最长长度,也就是要找最长的公共子序列

既然是两个字符串,我们很容易想到dp表应该是一个二维的dp表

dp[i][j]中i是str1的下标,j是str2的下标

根据经验,我们会设出这样的状态表示
dp[i][j]表示str1以i位置为结尾的区间和str2以j位置为结尾的区间内,公共子序列的最长长度

如果以这个状态表示去分析状态转移方程,就会发现错误:

  • 如果s[i] == s[j] ,则可以构成公共子序列,此时只需在i-1和j-1区间内求得最长的公共子序列的长度然后再加上1即可,所以 dp[i][j] = dp[i - 1][j - 1] + 1
  • 如果 s[i] != s[j] ,此时就无法构成公共子序列,但是状态表示明确指出str1必须以i为结尾,str2必须以j为结尾,也就是公共子序列必须以这两个字符为结尾,逻辑矛盾,无法求出状态转移方程

所以我们要想办法更新一个状态转移方程,分析上述过程,最大的矛盾点在于两个公共子序列不能严格的按照以xxxx为结尾的形式表示,而是应该不限制子序列的开始结束位置,所以可以将状态表示设置为如下:
dp[i][j]:表示str1[0,i]区间内的字符串和str2[0,j]区间内的字符串中,最长的公共子序列的长度

状态转移方程推导:

  • 如果s[i] == s[j],则这两个区间内最长的公共子序列一定以(i,j)为结尾;可以利用反证法证明
    1. 如果不是以(i,j)为结尾,那么最长的公共子序列可以在内部,但是又由于s[i]==s[j],他们俩也算是公共子序列的一部分,所以还是以s[i]为结尾
    2. 还有可能是以(i,j)中一个下标为结尾,另一个不是最长公共子序列的结尾,但是由于,此时还是一定以(i,j)为结尾的
      在这里插入图片描述
  • 如果s[i] != s[j],也就是结束的两个字符不同,则最长的公共子序列一定不以这两个位置为结尾,而是以i或者j之前的区间内的某一个位置为结尾,可以分三种情况:
    1. [i-1][j]
    2. [i][j - 1]
    3. [i - 1][j - 1]

dp[i][j]应取这三种情况的最大值

在这里插入图片描述

初始化

初始化的目的就是为了防止越界,本题可能出现越界的情况是当i,j为0时

对于二维dp的问题,最常用的一种初始化的方式就是增加一行,增加一列-->dp[m + 1][n + 1]

增加之后就要考虑如何为这些位置赋值了,我们赋值的原则应该是:赋的值应该对之后的填表无影响,或者根据dp表所表示的实际的意义去赋值,本题就利用到这样的想法

试想,第一行表示i==0的情况,此时str1为空字符串(注意下标之间的映射关系),那么根据dp表的含义,此时两个字符串之间不存在公共的子序列,进而也不存在最长的公共子序列长度这一说,所以第一行的所有值应该赋值为0,同样的第一列也要赋值为0
在这里插入图片描述

还需要注意的一点是:如果我们扩增了dp表,则dp表与源字符串之间的映射关系发生改变,dp[i + 1] = str[i],dp表的i位置对应的是字符串的的i-1位置,其实这里也可以做一个小优化(字符串的dp问题经常会使用这样的优化),就是让原先的字符串扩增1,str1 = " " + str1,str2 = " " + str2,让两个字符串都拼接一个空格字符,这样他们的长度就+1了,此时dp表的i下标对应的就是字符串的i下标

填表顺序

易得:从上往下,从左至右

返回值

return dp[m][n]

  • m == str1.length();
  • n == str2.length();

代码实现:

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        // 1.创建dp表
        int m = text1.length();
        int n = text2.length();
        int[][] dp = new int[m + 1][n + 1];

        // 2.初始化
        text1 = " " + text1;
        text2 = " " + text2;
        char[] s1 = text1.toCharArray();
        char[] s2 = text2.toCharArray();

        // 3.填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]);
            }
        }

        // 4.返回值
        return dp[m][n];
    }
}

2.不相交的线

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

分析:

本题的思路和"最长的公共子序列"那道题目的解法相同

代码:

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        // 本题的思路和"最长的公共子序列"那道题目的解法相同
        int m = nums1.length;
        int n = nums2.length;
        int[][] dp = new int[m + 1][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] = Math.max(dp[i - 1][j],dp[i][j - 1]);
            }
        }

        return dp[m][n];
    }
}

3.不同的⼦序列

链接:
https://leetcode.cn/problems/distinct-subsequences/submissions/516072259/

分析:

对于两个字符串,公共序列xxxx之类的问题,我们用经验来作为状态表示,本题的状态表示:

  • dp[i][j]:表示s字符串[0,j]区间内包含多少个t字符串[0,i]区间的字符

首先,这个状态表示能返回最终的结果么?可以的,走到最后,就表示s整个字符串内包含多少个t字符串,刚好和题目要求相同

接着分析状态转移方程,对于本题状态转移方程还是有所不同的,首先由于是在s中找有多少个t这样的要求,那么t一定是较小的那个,对于t字符串来说,每次推导状态,都必须包含i位置的字符,注意不是找有多少个公共序列,而是找s中包含多少个t

状态转移方程的推导一般都是根据最后一个状态进行划分,对于t来说,其状态是固定的,不用考虑,对于s来说需要分类讨论,因为包不包含最后一个位置的字符是对整个状态有影响的,所以可以分为以下两种情况

  • 包含s[j]:也就是s字符串的子序列必须以j位置的字符结尾,那么此时dp[i][j]的生效就有条件了,必须t[i] == s[j],dp[i][j]才能生效,且dp[i][j] = dp[i - 1][j - 1]
  • 不包含 s[j]:在s字符串的[0,i-1]区间内找t字符串[0,i]出现的次数

初始化

还是根据经验,二维的dp一般选择增加一行一列的方式来规避越界,第一行表示i == 0,即t字符串为空串,所以第一行全部初始化为1,第一列表示j == 0,即s字符串为空串,第一行全部初始化为0

返回值

易得返回dp[m][n]

在这里插入图片描述

代码:

class Solution {
    public int numDistinct(String s, String t) {
        // 特殊判断
        if(t.length() > s.length()) return 0;

        // 创建dp表并初始化
        int m = t.length();
        int n = s.length();
        int[][] dp = new int[m + 1][n + 1];
        for(int j = 0; j <= n; j++) dp[0][j] = 1;
        
        
        t = " " + t;
        s = " " + s;
        char[] tt = t.toCharArray();
        char[] ss = s.toCharArray();
        
        // 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = tt[i] == ss[j] ? (dp[i][j - 1] + dp[i - 1][j - 1]) : dp[i][j - 1];
            }
        }
        
        return dp[m][n];
    }
}

4.通配符匹配

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

分析:
在这里插入图片描述

代码:

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];

        // 2.初始化
        dp[0][0] = true;
        for(int j = 1; j <= n; j++){
            if(p.charAt(j - 1) == '*') dp[0][j] = true;
            else break;
        }
        s = " " + s;
        p = " " + p;
        char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();

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

本题的难点就在于当p[j] == '*'时可以匹配任意的子序列 ,那么就有很多种的状态表示,要想办法使用若干个状态去表示.

5. 正则表达式

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

分析:
初看本题觉得和上一题通配符匹配很相似,于是直接C,V结果发现无法通过(大胆),经过仔细分析发现本题在p[j] == '*'这种情况和上一题不同,上一题的*可以匹配任意的子序列,也就是他的状态是不受到之前状态的影响的,但是本题不一样,题目中明确告知*必须和前一个字符结合才有意义
在这里插入图片描述
也就是说,如果p[j] == *,其状态会受到p[j - 1]的影响,所以对于这种情况要单独讨论
在这里插入图片描述

一定要注意*可以匹配空串,此时就代表这两个位置的字符无效了

初始化:

本题的初始化和通配符匹配也有所不同,还是那句话,这道题当p[j]==*时的状态是受到前一个字符的影响的
在这里插入图片描述

注意本题是不会出现多个*连续出现的,题目规定一个*之前一定有一个有效的字符去进行匹配
在这里插入图片描述

代码:

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];

        // 2.初始化(注意细节)
        dp[0][0] = true;
        for(int j = 2; j <= n; j+= 2){
            if(p.charAt(j - 1) == '*') dp[0][j] = true;
            else break;
        }
        s = " " + s;
        p = " " + p;
        char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();

        // 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(pp[j] != '*') dp[i][j] = (ss[i] == pp[j] || pp[j] == '.') && dp[i - 1][j - 1];
                else dp[i][j] = dp[i][j - 2] || (pp[j - 1] == '.' || pp[j - 1] == ss[i]) && dp[i - 1][j];
            }
        }

        // 返回值
        return dp[m][n];

    }
}

总结:

  1. 两个数组的dp问题经常是两个字符串之间关系,比如公共子序列的长度,能够匹配多少个目标字符串之类的
  2. 两个字符串的问题也有一些常用的经验和优化
    • 状态表示一般都是s1[0,1]区间内,s2[0,j]区间内巴拉巴拉,比如s1.s2在不同的区间时的最长公共子序列的长度,又或者s2在在不同区间内能包含多少个s1特定区间内的字符串这样的问题,和之前我们惯用的以i位置为结束的状态表示不同
    • 状态转移方程的推到比较难,要结合具体的题目尽心分析,但是大致的方向都相同,即根据最后一个位置的状态去分类讨论
    • 在初始化时往往要引入空串,来应对下标之间的映射关系.对于dp表往往采取增加一行一列的方式进行初始化
    • 返回值一般就是返回dp表中最后一个元素

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

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

相关文章

c++之旅第八弹——多态

c++之旅第八弹——多态

大家好啊&#xff0c;这里是c之旅第八弹&#xff0c;跟随我的步伐来开始这一篇的学习吧&#xff01; 如果有知识性错误&#xff0c;欢迎各位指正&#xff01;&#xff01;一起加油&#xff01;&#xff01; 创作不易&#xff0c;希望大家多多支持哦&#xff01; 一&#xff0…
阅读更多...
AI研报：从Sora看多模态大模型发展

AI研报：从Sora看多模态大模型发展

《从Sora看多模态大模型发展》的研报来自浙商证券&#xff0c;写于2024年2月。 这篇报告主要探讨了多模态大模型的发展趋势&#xff0c;特别是OpenAI发布的视频生成模型Sora&#xff0c;以及其对行业发展的影响。以下是报告的核心内容概述&#xff1a; Sora模型的发布&#x…
阅读更多...
【C++航海王：追寻罗杰的编程之路】queue

【C++航海王：追寻罗杰的编程之路】queue

目录 1 -> queue的介绍和使用 1.1 -> queue的介绍 1.2 -> queue的使用 1.3 -> queue的模拟实现 1 -> queue的介绍和使用 1.1 -> queue的介绍 queue的文档介绍 1. 队列是一种容器适配器&#xff0c;专门用于在FIFO(先进先出)上下文中操作&#xff0c;其…
阅读更多...
C语言例4-4：putchar()函数的调用格式和使用的例子

C语言例4-4：putchar()函数的调用格式和使用的例子

代码如下&#xff1a; //putchar()函数的调用格式和使用的例子 #include<stdio.h> //编译预处理命令&#xff0c;即文件包含命令 int main(void) {char ch1N, ch2E, ch3W;putchar(ch1);putchar(ch2);putchar(ch3); //输出变量c1、c2和c3中的字符putchar(\n);putcha…
阅读更多...
Protocol Buffers设计要点

Protocol Buffers设计要点

概述 一种开源跨平台的序列化结构化数据的协议。可用于存储数据或在网络上进行数据通信。它提供了用于描述数据结构的接口描述语言&#xff08;IDL&#xff09;&#xff0c;也提供了根据 IDL 产生代码的程序工具。Protocol Buffers的设计目标是简单和性能&#xff0c;所以与 XM…
阅读更多...
长安链共识算法切换：动态调整，灵活可变

长安链共识算法切换：动态调整，灵活可变

#功能发布 长安链3.0正式版发布了多个重点功能&#xff0c;包括共识算法切换、支持java智能合约引擎、支持后量子密码、web3生态兼容等。我们接下来为大家详细介绍新功能的设计、应用与规划。 随着长安链应用愈加成熟与广泛&#xff0c;一些在生产中很实用的需求浮出水面。长安…
阅读更多...
MySQL进阶-----索引的结构与分类

MySQL进阶-----索引的结构与分类

目录 前言 一、认识索引 二、索引结构 1.概述 2. 二叉树 3 .B-Tree 4.BTree 5.Hash 三、索引的分类 1 .索引分类 2 .聚集索引&二级索引 前言 索引&#xff08;index&#xff09;是帮助MySQL高效获取数据的数据结构(有序)。在数据之外&#xff0c;数据库系统还维…
阅读更多...
基于nginx 动态 URL反向代理的实现

基于nginx 动态 URL反向代理的实现

背景&#xff1a; 我们在项目中在这样一个场景&#xff0c;用户需要使用固定的软件资源&#xff0c;这些资源是以服务器或者以容器形式存在的。 资源以webAPI方式在内网向外提供接口&#xff0c;资源分类多种类型&#xff0c;每种类型的资源程序和Wapi参数都一样。这些资源部属…
阅读更多...
javaWeb在线考试系统

javaWeb在线考试系统

一、简介 在线考试系统是现代教育中一项重要的辅助教学工具&#xff0c;它为学生提供了便捷的考试方式&#xff0c;同时也为教师提供了高效的考试管理方式。我设计了一个基于JavaWeb的在线考试系统&#xff0c;该系统包括三个角色&#xff1a;管理员、老师和学生。管理员拥有菜…
阅读更多...
ubuntu2004自动更新内核导致nvidia驱动无法正常启动的问题

ubuntu2004自动更新内核导致nvidia驱动无法正常启动的问题

症状 开机后&#xff0c;nvidia-smi无法正常显示显卡状态&#xff0c;另外无法连接多个显示屏 解决 参考这个文章&#xff1a; ls /usr/src可以看到已安装的nvidia驱动版本是nvidia-535.54.03 然后运行下面的指令&#xff1a; sudo apt-get install dkmssudo dkms instal…
阅读更多...
Mimikatz介绍

Mimikatz介绍

一、Mimikatz定义 mimikatz是benjamin使用C语言编写的一款非常强大的安全工具&#xff0c;它可以从机器内存中提取明文密码、密码Hash、PIN码和Kerberos票据等。它的功能非常强大&#xff0c;得到全球安全研究员的广泛使用。 Mimikatz 是一款功能强大的轻量级调试神器&#xff…
阅读更多...
Java版直播商城免 费 搭 建：平台规划与常见营销模式，电商源码、小程序、三级分销及详解

Java版直播商城免 费 搭 建：平台规划与常见营销模式，电商源码、小程序、三级分销及详解

【saas云平台】打造全行业全渠道全场景的saas产品&#xff0c;为经营场景提供一体化解决方案&#xff1b;门店经营区域化、网店经营一体化&#xff0c;本地化、全方位、一站式服务&#xff0c;为多门店提供统一运营解决方案&#xff1b;提供丰富多样的营销玩法覆盖所有经营场景…
阅读更多...
在vue中使用echarts饼图示例

在vue中使用echarts饼图示例

1.安装 npm install echarts --save 2.官方示例 option {title: {text: Referer of a Website,subtext: Fake Data,left: center},tooltip: {trigger: item},legend: {orient: vertical,left: left},series: [{name: Access From,type: pie,radius: 50%,data: [{ value: 104…
阅读更多...
巧用cpl文件维权和免杀（下）

巧用cpl文件维权和免杀（下）

cpl文件的应用 bypass Windows AppLocker 什么是Windows AppLocker: AppLocker即“应用程序控制策略”&#xff0c;是Windows 7系统中新增加的一项安全功能。在win7以上的系统中默认都集成了该功能。 默认的Applocker规则集合,可以看到cpl并不在默认规则中: 开启Applocker规…
阅读更多...
NVIDIA NIM 提供优化的推理微服务以大规模部署 AI 模型

NVIDIA NIM 提供优化的推理微服务以大规模部署 AI 模型

NVIDIA NIM 提供优化的推理微服务以大规模部署 AI 模型 生成式人工智能的采用率显着上升。 在 2022 年 OpenAI ChatGPT 推出的推动下&#xff0c;这项新技术在几个月内就积累了超过 1 亿用户&#xff0c;并推动了几乎所有行业的开发活动激增。 到 2023 年&#xff0c;开发人员…
阅读更多...
聊一聊常见的网络安全模型

聊一聊常见的网络安全模型

目录 一、概述 二、基于时间的PDR模型 2.1 模型概念提出者 2.2 模型图 2.3 模型内容 2.3.1 Protection&#xff08;保护&#xff09; 2.3.2 Detection&#xff08;检测&#xff09; 2.3.3 Response&#xff08;响应&#xff09; 2.4 PDR模型思想 2.4.1 PDR模型假设 2…
阅读更多...
【k8s】kubeasz 3.6.3 + virtualbox 搭建本地虚拟机openeuler 22.03 三节点集群 离线方案

【k8s】kubeasz 3.6.3 + virtualbox 搭建本地虚拟机openeuler 22.03 三节点集群 离线方案

kubeasz项目源码地址 GitHub - easzlab/kubeasz: 使用Ansible脚本安装K8S集群&#xff0c;介绍组件交互原理&#xff0c;方便直接&#xff0c;不受国内网络环境影响 拉取代码&#xff0c;并切换到最近发布的分支 git clone https://github.com/easzlab/kubeasz cd kubeasz gi…
阅读更多...
【openGL4.x手册10】基元程序集和面部剔除

【openGL4.x手册10】基元程序集和面部剔除

https://www.khronos.org/opengl/wiki/Face_Culling 一、说明 基元汇编是 OpenGL 渲染管道中的阶段&#xff0c;在该阶段&#xff0c;基元被划分为一系列单独的基本基元。经过一些小的处理后&#xff0c;如下所述&#xff0c;它们被传递到光栅器进行渲染。 二 早期原始组装 基…
阅读更多...
Spring实例化Bean的三种方式

Spring实例化Bean的三种方式

参考资料&#xff1a; Core Technologies 核心技术 spring实例化bean的三种方式 构造器来实例化bean 静态工厂方法实例化bean 非静态工厂方法实例化bean_spring中有参构造器实例化-CSDN博客 1. 构造函数 1.1. 空参构造函数 下面这样表示调用空参构造函数&#xff0c;使用p…
阅读更多...
npm ERR! cb() never called!(已解决)

npm ERR! cb() never called!(已解决)

从仓库拉下来的代码&#xff0c;用npm install时报错 试了很多种方法&#xff0c;结果发现有一种可能是你的node版本过低导致的&#xff0c;可以升级node版本试一下。 node版本升级后&#xff0c;把上一次npm install错误的node_modules删除&#xff0c;重新npm install。
阅读更多...
最新文章

Copyright @ 2022~2023