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

目录

一、最长公共子序列

二、不同的子序列

三、通配符匹配

四、正则表达式匹配

五、两个字符串的最小ASCII删除和

六、最长重复子数组

七、交错字符串

一、最长公共子序列

最长公共子序列

第一步：确定状态表示

dp[i][j]：表示字符串 s1 的 [0，i] 区间以及字符串 s2 的[0，j] 区间内所有子序列中，最长公共子序列的长度。

第二步：推出状态转移方程

第三步：初始化dp表

关于字符串的 dp 问题，我们需要考虑空串的情况，比如 s1 选一个空串，s2 选一个空串，其实也属于是一个公共子序列，不过公共子序列长度为0。

我们可以在原始 dp 表上多加一行一列，第0行表示第一个字符串为空，第0列表示第二个字符串为空。

让dp表多加了一行和一列后，我们需要注意dp表的下标和字符串下标的对应关系。 

解题代码：

class Solution 
{
public:
    int longestCommonSubsequence(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++)
            {
                if(s1[i-1] == s2[j-1])
                    dp[i][j] = dp[i-1][j-1] + 1;
                else
                    dp[i][j] = max(dp[i-1][j], max(dp[i][j-1], dp[i-1][j-1]));
            }
        }
        return dp[m][n];
    }
};

 

二、不同的子序列

不同的子序列

第一步：确定状态表示

dp[i][j]：表示s字符串 [0，i]区间内所有子序列中，有多少个t字符串 [0，j] 区间内的子串。

第二步：推出状态转移方程

第三步：初始化dp表。

我们需要考虑空串的情况，比如 s1 选一个空串，s2 选一个空串，其实也属于是一个公共子序列。

第一行表示 s 字符串为空串，s 如果是空串，t 只有是空串，才能在 s 中找到 t。第一列表示 t 字符串为空串，t 如果是空串，s 不管是什么字符串，它里面都有一个空串。因此第一列应该全都是1。

解题代码：

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

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

 

三、通配符匹配

通配符匹配

第一步： 确定状态表示

dp[i][j]：表示p[0，i] 区间内的子串能否匹配 s[0，j] 区间内的子串。

第二步：推出状态转移方程

第三步：初始化dp表

如果s是空字符串，p字符串前面出现 ’ * ‘ 可以匹配空串，但是 ’ * ‘ 之后如果出现其他字符了，后面不管有多少个’ * '都不能匹配了。

dp[i][j]表示p[0，i] 区间内的子串能否匹配 s[0，j] 区间内的子串。题目要求是整个字符串，因此返回dp[m][n]，m是s的长度，n是p的长度。

解题代码：

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

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

 

四、正则表达式匹配

正则表达式匹配

第一步：确定状态表示

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

第二步：推出状态转移方程

第三步：初始化dp表

dp表上面多加一行表示p是空串，左边多加一列表示s是空串。接下来看看里面值应该填什么。

对于第一行，如果p是空串，s也是空串，肯定能匹配，所以第一行第一个空格还是true。

后续如果 p 是空串，s不是空串，肯定匹配不上，所以第一行后续都是false。

解题代码：

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

            if(p[i] == '*' && p[i-1] != '*')
                dp[i][0] = true;
        }

        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(p[i] >= 'a' && p[i] <= 'z')
                {
                    if(p[i] == s[j] && dp[i-1][j-1] == true)
                        dp[i][j] = true;
                }
                else if(p[i] == '.')
                    dp[i][j] = dp[i-1][j-1];
                else
                {
                    if(p[i-1] == '.')
                        dp[i][j] = dp[i-2][j] || dp[i][j-1];
                    else
                        dp[i][j] = dp[i-2][j] || (s[j] == p[i-1] && dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
    }
};

 

五、两个字符串的最小ASCII删除和

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

预处理：本道题是让我们找使两个字符串相等，所需删除字符的ASCII值最小。而最开始的两个字符串的ASCII值总和是不变的，那么我们只需要找到两个字符串相同后，其ASCII值最大，那么删除的字符的ASCII值一定就是最小的。

所以说，该问题就转化成了：求两个字符串的所有公共子序列里面，ASCII值的最大和。

第一步：确定状态表示

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

第二步：推出状态转移方程

对于s1[0，i]区间和s2[0，j]区间的公共子序列有四种情况，即：

有s1[i]，有s2[j]

有s1[i]，没有s2[j]

没有s1[i]，有s2[j]

没有s1[i]，没有s2[j]

情况四可以包含在情况二中。

第三步：初始化dp表

第四步：确定返回值

状态表示求的是两个字符串的区间里面公共子序列的ASCII值最大和。

而题目要求使两个字符串相等所需删除字符的ASCII值的最小和 。所以可以这样做：

1、找到两个字符串中公共子序列的Ascll 最大和，dp[m][n]。

2、统计两个字符串中ASCII值总和，sum。

3、sum - dp[m][n] * 2。

解题代码：

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

 

六、最长重复子数组

最长重复子数组

第一步：确定状态表示

dp[i][j]：表示数组 nums1 中以 i 位置元素为结尾的所有的子数组以及数组 nums2 中以 j 位置元素为结尾的所有子数组中，最长公共子数组的长度。

第二步：推出状态转移方程

第三步：初始化dp表

填写顺序：根据状态转移方程。从上往下填写每一行。 最后的返回值是 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;
    }
};

七、交错字符串

交错字符串

预处理：为了下标对应，我们给每个字符串的前面都加上一个空格字符。 

第一步：确定状态表示

dp[i][j]：表示s1[1，i]区间内的字符串和s2[1，j]区间内的字符串能不能拼成s3[1，i+j]区间内的字符串。

第二步：推出状态转移方程

第三步：初始化dp表

解题代码：

class Solution 
{
public:
    bool isInterleave(string s1, string s2, string s3) 
    {
        int m = s1.size(),  n = s2.size();
        if(m+n != s3.size())
            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++)
            {
                if(s1[i] == s3[i+j] && dp[i-1][j])
                    dp[i][j] = true;
                else if(s2[j] == s3[i+j] && dp[i][j-1])
                    dp[i][j] = true;
            }
        }
        return dp[m][n];
    }
};

 

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

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

相关文章

安卓13默认连接wifi热点 android13默认连接wifi

安卓13默认连接wifi热点 android13默认连接wifi

总纲 android13 rom 开发总纲说明 文章目录 1.前言2.问题分析3.代码分析4.代码修改5.编译6.彩蛋1.前言 有时候我们需要让固件里面内置好，相关的wifi的ssid和密码，让固件起来就可以连接wifi，不用在手动操作。 2.问题分析 这个功能，使用普通的安卓代码就可以实现了。 3.代…
阅读更多...
Kubernetes：（三）Kubeadm搭建K8s 1.20集群

Kubernetes：（三）Kubeadm搭建K8s 1.20集群

文章目录 一、Kubeadm安装流程二、实验1.环境准备2.所有节点安装kubeadm&#xff0c;kubelet和kubectl&#xff08;除了Harbor节点&#xff09;3.部署 Dashboard4.安装Harbor私有仓库 一、Kubeadm安装流程 集群名称IP地址安装软件master&#xff08;2C/4G&#xff0c;cpu核心数…
阅读更多...
杨传辉：云+AI 时代的一体化数据库｜OceanBase发布会实录

杨传辉：云+AI 时代的一体化数据库｜OceanBase发布会实录

在 2024 OceanBase 年度发布会 上&#xff0c; OceanBase CTO 杨传辉进行了主题为《云和 AI 时代的一体化数据库战略思考》的演讲&#xff0c;本文为演讲实录&#xff0c;欢迎阅读。 视频观看可点击&#xff1a;https://www.oceanbase.com/video/9001825 各位 OceanBase 的客…
阅读更多...
ChatGPT变AI搜索引擎！以后还需要谷歌吗？

ChatGPT变AI搜索引擎！以后还需要谷歌吗？

前言 在北京时间11月1日凌晨&#xff0c;正值ChatGPT两岁生日之际&#xff0c;OpenAI宣布推出最新的人工智能搜索体验&#xff01;具备实时网络功能&#xff01;与 Google 展开直接竞争。 ChatGPT搜索的推出标志着ChatGPT成功消除了即时信息这一最后的短板。 这项新功能可供 …
阅读更多...
QT——记事本项目

QT——记事本项目

目录 1.给pushButton按键添加图片 1.1 首先复制存放图片的文件夹&#xff0c;打开Qt回到编辑页面&#xff0c;右键单击pro文件选择在Explorer中显示&#xff0c;将图片文件夹粘贴进去你的代码同目录即可 1.2 创建一个新的文件夹 1.3 点击Add Files&#xff0c;将所有图片添加…
阅读更多...
【在Linux世界中追寻伟大的One Piece】Socket编程TCP(续)

【在Linux世界中追寻伟大的One Piece】Socket编程TCP(续)

目录 1 -> V2 -Echo Server多进程版本 2 -> V3 -Echo Server多线程版本 3 -> V3-1 -多线程远程命令执行 4 -> V4 -Echo Server线程池版本 1 -> V2 -Echo Server多进程版本 通过每个请求&#xff0c;创建子进程的方式来支持多连接。 InetAddr.hpp #pragma…
阅读更多...
为什么可视化大屏要有动态效果，都有哪些类型的效果。

为什么可视化大屏要有动态效果，都有哪些类型的效果。

可视化大屏已成为企业和组织展示关键信息的重要工具。这些大屏不仅需要清晰地传达数据&#xff0c;还要吸引观众的注意力并提供深刻的洞察。动态效果在这一过程中扮演着至关重要的角色。 动态效果的重要性 动态效果在可视化大屏中的应用&#xff0c;基于以下几个核心原因 吸…
阅读更多...
【C/C++】字符/字符串函数（0）（补充）——由ctype.h提供

【C/C++】字符/字符串函数（0）（补充）——由ctype.h提供

零.导言 除了字符分类函数&#xff0c;字符转换函数也是一类字符/字符串函数。 C语言提供了两种字符转换函数&#xff0c;分别是 toupper &#xff0c; tolower。 一.什么是字符转换函数&#xff1f; 顾名思义&#xff0c;即转换字符的函数&#xff0c;如大写字母转小写字母&am…
阅读更多...
Hive数据库操作语法

Hive数据库操作语法

数据类型 内部表和外部表 内部表 &#xff08;CREATE TABLE table_name ......&#xff09;未被external关键字修饰的即是内部表&#xff0c; 即普通表。 内部表又称管理表,内部表数据存储的位置由hive.metastore.warehouse.dir参数决定&#xff08;默认&#xff1a;/user/h…
阅读更多...
线程基础知识、jmm（Java内存模型）

线程基础知识、jmm（Java内存模型）

目录 线程基础知识 并发与并行 进程和线程 线程优先级 创建线程的方式主要有三种 休眠 作出让步 join() 方法 线程协作注意什么 理解线程状态 选择合适的协作工具 共享资源的访问控制 避免竞争条件 创建线程几种方式 线程状态&#xff0c;状态之间切换 新建&…
阅读更多...
图解大模型训练系列：序列并行2，DeepSpeed Ulysses

图解大模型训练系列：序列并行2，DeepSpeed Ulysses

最近已有不少大厂都在秋招宣讲&#xff0c;也有一些已在 Offer 发放阶段了。 节前&#xff0c;我们邀请了一些互联网大厂朋友、今年参加社招和校招面试的同学。 针对新手如何入门算法岗、该如何准备面试攻略、面试常考点、大模型技术趋势、算法项目落地经验分享等热门话题进行…
阅读更多...
MP4650模块改为固定电压记录

MP4650模块改为固定电压记录

目标 这种电源模块&#xff0c;可调电位器质量不太好&#xff0c;可调输出电压改为固定电压。 方法 步骤 按照下图&#xff0c;将计算得到的R1 补到 待添加电阻处。 结论 作者使用输出5V&#xff0c;R1电阻使用5.1K&#xff0c;得到输出电压4.8V&#xff1b; 测试输出电流1A…
阅读更多...
51单片机教程（二）- 创建项目

51单片机教程（二）- 创建项目

1 创建项目 创建项目存储文件夹&#xff1a;C51Project 打开Keil5软件&#xff0c;选择 Project -> New uVision Project&#xff1a; 选择项目路径&#xff0c;即刚才创建的文件夹 选择芯片&#xff0c;选择 Microchip&#xff08;微型集成电路&#xff09;&#xff0…
阅读更多...
STM32 HAL库 SPI驱动1.3寸 OLED屏幕

STM32 HAL库 SPI驱动1.3寸 OLED屏幕

目录 参考硬件引脚与接线 点亮屏幕CubeMX 配置OLED 驱动程序代码 参考 基于STM32F103C8T6最小系统板HAL库CubeMX SPI驱动7针 OLED显示屏&#xff08;0.96寸 1.3寸通用&#xff09;0.96 oled HAL库驱动 SPI STM32SPI驱动0.96/1.3寸 OLED屏幕&#xff0c;易修改为DMA控制STM32驱…
阅读更多...
通过分解质因数求若干个数的最小公倍数

通过分解质因数求若干个数的最小公倍数

求最小公倍数的常规方法回顾 暴力枚举法 long long work(long long a,long long b) {for(long long imax(a,b);;i)if(i%a0&&i%b0)return i; }大数翻倍法 long long work(long long a,long long b) {if(a<b) swap(a,b);for(long long ia;;ia) // i 是 a 的倍数&#…
阅读更多...
突出显示与条件匹配的列值

突出显示与条件匹配的列值

Goto Appearance and Conditional Formatting 外观和条件格式 突出显示与条件匹配的列值 本教程说明如何将条件格式应用于 GridControl 中的 Market Share 列&#xff0c;以突出显示与特定条件匹配的单元格。此示例突出显示小于 20% 的 Market Share 列值。 要在设计时创建新…
阅读更多...
node.js下载、安装、设置国内镜像源（永久）（Windows11）

node.js下载、安装、设置国内镜像源（永久）（Windows11）

目录 node-v20.18.0-x64工具下载安装设置国内镜像源&#xff08;永久&#xff09; node-v20.18.0-x64 工具 系统&#xff1a;Windows 11 下载 官网https://nodejs.org/zh-cn/download/package-manager 版本我是跟着老师选的node-v20.18.0-x64如图选择 Windows、x64、v20.18…
阅读更多...
嵌入式开发教程之Linux下IO流

嵌入式开发教程之Linux下IO流

一、文件的概念和类型 文件基础&#xff1a; 概念&#xff1a;一组相关数据的有序集合&#xff0c;文件名、路径。通过文件名指定访问什么文件。 文件类型&#xff1a; 常规文件 r&#xff0c;分为&#xff1a;普通文件&#xff0c;文本文件&#xff08;可见字符&#xff09…
阅读更多...
【Python】Python自习课：第一个python程序

【Python】Python自习课：第一个python程序

【Python】Python自习课&#xff1a;第一个python程序
阅读更多...
MySQL【二】

MySQL【二】

查询列 SELECT [ALL | DISTINCT ] * | 列名1[,……列名n] FROM 表名; 查询所有选课学生的学号&#xff0c;结果去除重复值 select distinct sno from sc; 选择行 查询满足条件的数据集 SELECT 字段列表 FROM 表名 WHERE 查询条件 查询不属于数学系或外国语系的学生全部信息 …
阅读更多...
最新文章

Copyright @ 2022~2023