【动态规划】两个数组的 dp 问题

1. 最长公共子序列

1143. 最长公共子序列

状态表示:

dp[i][j] 表示 s1 的 0 ~ i 区间和 s2 的 0 ~ j 区间内所有子序列中,最长公共子序列的长度

状态转移方程:

当 s1[i] 和 s2[j] 相等时,那么最长公共子序列一定是以这两个位置为结尾的,所以就可以直接取 i - 1 ~ j - 1 区间内再去找,dp[i - 1][j - 1] 的结果加上确定好的 1 即可,如果不相等的话,就可以去 s1 的 i - 1 位置和 s2 的 j 继续找,或者是从 s1 的 i 位置和 s2 的 j - 1位置找,i - 1, j - 1 的情况已经被包含在这两种情况中了,所以可以不考虑这种情况,上面的情况找出最大值就是不相等时的 dp[i][j]

初始化:为了防止不越界,可以把数组多开一行和一列,初始化为 0 即可

填表顺序:从左到右,从上到下

返回值:dp[m][n]

class Solution {
    public int longestCommonSubsequence(String t1, String t2) {
        int m = t1.length(),n = t2.length();
        char[] s1 = t1.toCharArray();
        char[] s2 = t2.toCharArray();
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 1;i <= m;i++){
            for(int j = 1;j <= n;j++){
                if(s1[i - 1] == s2[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. 不相交的线

1035. 不相交的线

和上一题一样

3. 不同的子序列

115. 不同的子序列

状态表示:

dp[i][j] :s 字符串[0 , j] 区间内所有的子序列中,有多少个 t 字符 [0 , i] 区间内的子串

当 t[i] ≠ s[j] 时,就要从 j - 1 位置开始找,因为需要找到子串 t 区间是连续的,所以 i 位置不能动,也就是 dp[i][j] = dp[i][j - 1],如果 t[i] = s[j] 时,那么就还需要加上 dp[i - 1][j - 1]

初始化:为了防止越界,需要多开一行和一列,那么 i = 0 时,也就是 t 是空串的话,s 中枚举到哪个位置都是会包含一种方案的,也就是 i = 0 时都需要初始化为 1

填表顺序:从左到右,从上到下

返回值:dp[n][m]

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

4. 通配符匹配

44. 通配符匹配

状态表示:

dp[i][j] 表示字符串 p [0 , j ] 区间内是否能匹配字符串 s 区间 [0 , i ] 区间内的子串

状态转移方程:

字符串 p 的 j 位置可以分为普通字符,? ,* 三种情况,当是普通字符时,就需要判断 s[i] 和 p[j] 是否相等,如果相等,并且 dp[i - 1][j - 1] 也是 true ,那么 dp[i][j] 就是 true,如果是 ? 的话,直接就等于 dp[i][j],如果是 * 的话,由于 * 可以匹配任意个字符,所以可以由之前的任意状态表示,但是这么多状态如果用循环来表示的话就可能超时,这种情况是可以优化一下的

可以通过数学变换来得出 dp[i][j] 是等于 dp[i][j] || dp[i - 1][j] 的

还可以用另一种思路:

' * ' 可以匹配空串,此时就要往 dp[i][j - 1] 中找答案,也可以匹配一个字符,但是不舍去,下一次还可以用来匹配一个字符或者空串,这样就达到了匹配多个字符的效果

初始化:可以通过引入空串的方式来初始化,防止填表时越界

(0 , 0 ) 位置肯定就是 true ,因为引入空串之后两个字符的 0 下标都是空字符串,可以匹配,但是当 j++ 时,也就是字符串 p 之后是 * 的话才能匹配空串,只要遇到不是 * ,后面都是 false,而第一列 1 下标之后,表示 p 的空串去匹配字符串 s ,肯定都是 false

填表顺序:从左到右

返回值:dp[m][n]

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

5. 正则表达式匹配

10. 正则表达式匹配

状态表示:

dp[i][j] 表示字符串 p[0 , j] 区间内的子串能否匹配字符串 s [0 , i ] 区间内的子串

状态转移方程:

根据最后一个字符的状态可以分为下面这几种情况

当字符串 p 最后一个字符是字母时,就需要判断是否和字符串 s 的 i 位置字符相等,相等的话就可以根据 dp[i - 1][j - 1] 来更新状态,如果是 ' . ' 的话,直接可以根据 dp[i - 1][j - 1] 来更新状态,如果是 ' * ' 的话,就需要考虑前一个字符是字母还是 ' . ',如果是 ' . ' 的话,就可以选择匹配空串,或者多个字符,就能更新出一堆状态,对于这样的状态表示,可以用上一题一样的优化方式,优化为 dp[i - 1][j] ,如果是字母的话,就需要判断是否能和 i 位置字符相等,然后选择匹配几个,同理,这种状态表示也可以优化为 dp[i - 1][j]

初始化:

第一列,也就是 p 是空串,这样除非 s 也是空串,否则怎么也不会匹配成功,所以只有 dp[0][0] 是 true,而对于第一行,如果说连续的偶数位上的字符是 ' * ' 的话,那么就可以带上前面的字符一起匹配空串,只要发现不是连续的偶数位,后面就都是 false

填表顺序:从上到下,从左到右

返回值:dp[m][n]

class Solution {
    public boolean isMatch(String ss, String pp) {
        int m = ss.length(),n = pp.length();
        ss = " " + ss;
        pp = " " + pp;
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        boolean[][] dp = new boolean[m + 1][n + 1];
        //初始化
        for (int i = 2; i <= n; i += 2){
            if(p[i] == '*'){
                dp[0][i] = true;
            }else{
                break;
            }   
        }
        dp[0][0] = true;
        //填表
        for (int i = 1; i <= m; i++){
            for (int j = 1; j <= n; j++){
                if (p[j] == '*'){
                    dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (p[j - 1] == '.' ||p[j - 1] == s[i]));
                }else{
                    dp[i][j] = dp[i - 1][j - 1] && (p[j] == s[i] || p[j] == '.');
                }
            }
        }
        return dp[m][n];
    }
}

6. 交错字符串

97. 交错字符串

状态表示:

为了方便进行表示,可以把三个字符串前面都加上一个空串,来更好的进行初始化和状态表示

dp[i][j] 表示 s1 中 [1 , i ] 区间内的字符串以及 s2 [ 1 , j ] 区间内的字符串,能否拼接成 s3 [1 , i + j ] 区间内的字符串

状态转移方程:

如果能拼接成功的话, s3 的最后一个位置一定是 s1 或者 s2 的最后一个字符,所以就可以分为两种情况,如果是 s1 的话,那么 dp[i][j] 就等于 dp[i - 1][j],同理,如果是 s2 的话,那么就是 dp[i][j - 1]

初始化:

初始化的时候,dp[0][i] 就表示 s1 是空串的情况,此时就是判断 s2 和 s3 各个位置上的字符是否相等,当遇到不相等的,后面所有的位置就都是 false, 同理,dp[i][0] 就表示 s2 是空串的情况

填表顺序:填当前位置时需要用到上一个位置的值,所以从上往下,从左往右依次填表

返回值:dp[m][n]

还有一个注意点就是,刚开始一定要判断如果 s1 和 s2 的长度和如果和 s3 的长度不相等就直接返回 false,不只是优化的问题,如果不添加的话,后续的填表也会有问题的

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length();
        if(m + n != s3.length()) return false;
        s1 = " " + s1;
        s2 = " " + s2;
        s3 = " " + s3;
        
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {
            if (s2.charAt(i) == s3.charAt(i)){
                dp[0][i] = true; 
            }else{
                break;
            }
        }
        for(int i = 1;i <= m;i++){
            if(s1.charAt(i) == s3.charAt(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.charAt(i) == s3.charAt(i + j) && dp[i - 1][j])||         
                (s2.charAt(j) == s3.charAt(i + j) && dp[i][j - 1]);               
            }
        }
        return dp[m][n];
    }
}

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

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

题中要求的是最小的 ASCII 删除和使剩下的字符串相等,那么就可以转化为公共子序列中最大的 ASCII 和,这样删除的 ASCII 和肯定就是最小的

状态表示:

dp[i][j] 表示 s1 的 [0 , i ] 区间和 s2 [0 , j ] 区间内的所有子序列中,公共子序列的 ASCII 最大和

状态转移方程:

可以分为四种情况,公共子序列中同时含有 s1 和 s2 的 i , j 位置的字符,以及只含其中一个,还有都不含的情况,由于是找最大值,都不包含的情况是被包含到只含一个的情况的,所以只需要求出前面三种情况的最大值即可

填表顺序:从左到右,从上到下

返回值:需要求出两个字符串的 ASCII 和,然后减去两倍的最大公共子序列的 ASCII 和

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length(),n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 1;i <= m;i++){
            for(int j = 1;j <= n;j++){
                dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]);
                if(s1.charAt(i - 1) == s2.charAt(j - 1))
                dp[i][j] = Math.max(dp[i][j],dp[i - 1][j - 1] + s1.charAt(i - 1)); 
            }
        }
        int sum = 0;
        for(char c : s1.toCharArray()) sum += c;
        for(char c : s2.toCharArray()) sum += c;
        return sum - 2 * dp[m][n];  
    }
}

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

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

相关文章

【计算机网络】【传输层】【习题】

计算机网络-传输层-习题 文章目录 10. 图 5-29 给出了 TCP 连接建立的三次握手与连接释放的四次握手过程。根据 TCP 协议的工作原理&#xff0c;请填写图 5-29 中 ①~⑧ 位置的序号值。答案技巧 注&#xff1a;本文基于《计算机网络》&#xff08;第5版&#xff09;吴功宜、吴英…

nacos集群部署与配置

Nacos集群模式 1. 预备环境准备 请确保是在环境中安装使用: 64 bit OS Linux/Unix/Mac&#xff0c;推荐使用Linux系统。64 bit JDK 1.8&#xff1b;下载. 配置。Maven 3.2.x&#xff1b;下载. 配置。3个或3个以上Nacos节点才能构成集群 ubuntu中假如没安装jdk&#xff0c;则…

Python学习从0到1 day26 第三阶段 Spark ③ 数据计算 Ⅱ

目录 一、Filter方法 功能 语法 代码 总结 filter算子 二、distinct方法 功能 语法 代码 总结 distinct算子 三、SortBy方法 功能 语法 代码 总结 sortBy算子 四、数据计算练习 需求&#xff1a; 解答 总结 去重函数&#xff1a; 过滤函数&#xff1a; 转换函数&#xff1a; 排…

Jmeter基础篇(23)TPS和QPS的异同

前言 这是一篇性能测试指标的科普文章哦&#xff01; TPS和QPS是同一个概念吗&#xff1f; TPS&#xff08;Transactions Per Second&#xff09;和QPS&#xff08;Queries Per Second&#xff09;虽然都是衡量系统性能的指标&#xff0c;但是它们并不是同一个概念。这两个各…

IEC60870-5-104 协议源码架构详细分析

IEC60870-5-104 协议源码架构 前言一、资源三、目录层级一二、目录层级二config/lib60870_config.hdependencies/READMEexamplesCMakeLists.txtcs101_master_balancedcs104_client_asyncmulti_client_servertls_clienttls_server说明 make这些文件的作用是否需要导入这些文件&a…

机器学习在网络安全中的应用

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 机器学习在网络安全中的应用 机器学习在网络安全中的应用 机器学习在网络安全中的应用 引言 机器学习概述 定义与原理 发展历程 …

JUC基础类-AbstractQueuedSynchronizer

AbstractQueuedSynchronizer 1、AbstractQueuedSynchronizer概述2、AbstractQueuedSynchronizer源码分析2.1 AQS源码2.2 Node类 如有侵权&#xff0c;请联系&#xff5e; 如有问题&#xff0c;也欢迎批评指正&#xff5e; 1、AbstractQueuedSynchronizer概述 AbstractQueuedSy…

文献阅读 | Nature Methods:使用 STAMP 对空间转录组进行可解释的空间感知降维

文献介绍 文献题目&#xff1a; 使用 STAMP 对空间转录组进行可解释的空间感知降维 研究团队&#xff1a; 陈金妙&#xff08;新加坡科学技术研究局&#xff09; 发表时间&#xff1a; 2024-10-15 发表期刊&#xff1a; Nature Methods 影响因子&#xff1a; 36.1&#xff0…

Redis系列之底层数据结构ZipList

Redis系列之底层数据结构ZipList 实验环境 Redis 6.0 什么是Ziplist&#xff1f; Ziplist&#xff0c;压缩列表&#xff0c;这种数据结构会根据存入数据的类型和大小&#xff0c;分配大小不同的空间&#xff0c;所以是为了节省内存而采用的。因为这种数据结构是一种完整连续…

界面控件DevExpress WPF中文教程:TreeList视图及创建分配视图

DevExpress WPF拥有120个控件和库&#xff0c;将帮助您交付满足甚至超出企业需求的高性能业务应用程序。通过DevExpress WPF能创建有着强大互动功能的XAML基础应用程序&#xff0c;这些应用程序专注于当代客户的需求和构建未来新一代支持触摸的解决方案。 无论是Office办公软件…

数据结构中数据有序性/ 单调性 ——二分查找

以下记录的都是闭区间写法 例题&#xff1a;34. 在排序数组中查找元素的第一个和最后一个位置 1.关系转换 寻找目标值有四种情况&#xff1a;≥、>、≤、< 比如目标值x&#xff0c; 可以转化为 ≥x、≥ x1、≤x、≤ x1 比如数组大小为6&#xff0c;目标值为…

探索Python的HTTP利器:Requests库的神秘面纱

文章目录 **探索Python的HTTP利器&#xff1a;Requests库的神秘面纱**一、背景&#xff1a;为何选择Requests库&#xff1f;二、Requests库是什么&#xff1f;三、如何安装Requests库&#xff1f;四、Requests库的五个简单函数使用方法1. GET请求2. POST请求3. PUT请求4. DELET…

《Linux从小白到高手》综合应用篇:深入详解Linux swap及其调整优化

1. 引言&#xff1a; Swap是存储设备上的一块空间&#xff08;分区&#xff09;&#xff0c;操作系统可以在这里暂存一些内存里放不下的东西。这从某种程度上相当于增加了服务器的可用内存。虽然从swap读写比内存慢&#xff0c;但总比没有好&#xff0c;算是内存不足时一种比较…

SpringMVC学习笔记(一)

一、SpringMVC的基本概念 &#xff08;一&#xff09;三层架构和MVC 1、三层架构概述 我们的开发架构一般都是基于两种形式&#xff0c;一种是 C/S 架构&#xff0c;也就是客户端/服务器&#xff0c;另一种是 B/S 架构&#xff0c;也就是浏览器服务器。在 JavaEE 开发中&…

小面馆叫号取餐流程 佳易王面馆米线店点餐叫号管理系统操作教程

一、概述 【软件资源文件下载在文章最后】 小面馆叫号取餐流程 佳易王面馆米线店点餐叫号管理系统操作教程 点餐软件以其实用的功能和简便的操作&#xff0c;为小型餐饮店提供了高效的点餐管理解决方案&#xff0c;提高了工作效率和服务质量 ‌点餐管理‌&#xff1a;支持电…

【.NET 8 实战--孢子记账--从单体到微服务】--简易权限--角色可访问接口管理

咱们继续来编写孢子记账的简易权限&#xff0c;这篇文章中我们将编写角色可访问接口的管理API&#xff0c;同样我不会把完整的代码全都列出来&#xff0c;只会列出部分代码&#xff0c;其余代码我希望大家能自己手动编写&#xff0c;然后对比项目代码。废话不多说&#xff0c;开…

Linux上Python使用MySQLdb包连接MySQL5.7和MySQL8的问题

在一台安装有MySQL8的Linux上用MySQLdb包连接MySQL5.7&#xff0c;连接参数中加上ssl_mode‘DISABLED’,能正常连接&#xff1b;不加ssl_mode参数&#xff0c;会报 而在连接MySQL8时加不加ssl_mode都能正常连接&#xff0c;但在使用过程&#xff0c;加了ssl_mode参数&#xff…

列表(list)

一、前言 本次博客主要讲解 list 容器的基本操作、常用接口做一个系统的整理&#xff0c;结合具体案例熟悉自定义内部排序方法的使用。如有任何错误&#xff0c;欢迎在评论区指出&#xff0c;我会积极改正。 二、什么是list list是C的一个序列容器&#xff0c;插入和删除元素…

spring使用xml文件整合事务+druid+mybatis

1.事务 事务&#xff08;Transaction&#xff09;是数据库管理系统中的一个重要概念&#xff0c;它表示一组不可分割的操作序列&#xff0c;这些操作要么全部执行成功&#xff0c;要么全部不执行&#xff0c;以确保数据库从一个一致性状态转换到另一个一致性状态。事务具有以下…

大语言模型LLM综述

一、LM主要发展阶段 1.1、统计语言模型SLM 基于统计学习方法&#xff0c;基本思想是基于马尔可夫假设HMM建立词概率预测模型。如n-gram语言模型 1.2、神经语言模型NLM 基于神经网络来做词的分布式表示。如word2vec模型 1.3、 预训练语言模型PLM 预训练一个网络模型来做词表…