DP：两个数组的dp问题

解决两个数组的dp问题的常用状态表示：

1、选取第一个字符串[0-i]区间以及第二个字符串[0,j]区间作为研究对象

2、根据题目的要求确定状态表示

字符串dp的常见技巧

1、空串是有研究意义的，引入空串可以帮助我们思考虚拟的边界如何进行初始化。

2、如果我们的dp多开了一行一列，可以在字符串的前面多加上一个空格（s=“ ”+s）,这样可以保证dp数组和字符串数组的下标映射关系是一一对应的，方便我们书写代码

一、最长公共子序列（模版）

. - 力扣（LeetCode）

算法原理：

1、状态表示（经验+题目要求）

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

 2、状态转移方程

dp[i][j]:  （从最后一个位置的状况去分情况讨论）

(1)s[i]==s[j]——>dp[i-1][j-1]+1

(2)s[i]!=s[j]——>max(dp[i-1][j],dp[i][j-1])              

注意：dp[i-1][j]和dp[i][j-1]都包含了dp[i-1][j-1]的情况，但是该题只需要找最大值而不是统计个数，所以不必在意。

3、初始化

多开一行一列，引入空串去研究边界，均初始化为0即可。

4、填表顺序

从上往下填每一行

每一行从左往右填

5、返回值

dp[m][n]

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        //字符串技巧
        int m=text1.size(),n=text2.size();
        text1=" "+text1, text2=" "+text2;
        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(text1[i]==text2[j]) dp[i][j]=dp[i-1][j-1]+1;
            else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        return dp[m][n];
    }
};

 二、不相交的线

. - 力扣（LeetCode）

该题其实等价于最长公共子序列 

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) 
    {
        //相当于是最长公共子序列
        int m=nums1.size(),n=nums2.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(nums1[i-1]==nums2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
            else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        return dp[m][n];
    }
};

三、不同的子序列

. - 力扣（LeetCode）

算法原理：

1、状态表示（经验+题目要求）

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

 2、状态转移方程

dp[i][j]:  （从s的子序列最后一个位置是否包含s[j]）

(1)包含s[j]——>t[i]==s[j]——>+=dp[i-1][j-1]

(2)不包含s[j]——>+=dp[i][j-1]            

3、初始化

引入空串去思考：

当s和t都为空串时，应该为1

当s为空串，t不为空串的时候，应该为0

当t为空串，s不为空串的时候，应该为1

所以t为空串时，也就是i=0（第一行） 应该都初始化为1  而其他位置则是0

4、填表顺序

从上往下填每一行

每一行从左往右填

5、返回值

dp[m][n]

6、细节处理

该题可能会越界，所以用double去存储。

class Solution {
public:
    int numDistinct(string s, string t) {
     //s字符串0-j中所有子序列中 有多少个t字符串内0-i区间内的子串
     int m=t.size(),n=s.size();
     vector<vector<double>> dp(m+1,vector<double>(n+1)); //会越界 double>long long
     //分析最后一位的状态  t[i]==s[j] dp[i-1][j-1]
     //无论如何dp[i][j]+=dp[i][j-1]
     //可以利用空串的性质去思考
     for(int j=0;j<=n;++j) dp[0][j]=1; 
     for(int i=1;i<=m;++i)
       for(int j=1;j<=n;++j)
         {
            dp[i][j]+=dp[i][j-1];
            if(t[i-1]==s[j-1]) dp[i][j]+=dp[i-1][j-1];
         }
         return dp[m][n];
    }
};

四、通配符匹配（重点）

. - 力扣（LeetCode）

 

class Solution {
public:
    bool isMatch(string s, string p) 
    {
      //两个数组的dp问题
      //p中0-j的子串能否匹配s中0-i的子串
      int m=s.size(),n=p.size();
      s=" "+s,p=" "+p;
      vector<vector<bool>> dp(m+1,vector<bool>(n+1));
      //初始化第一行 当s为空（i=0时） 
      dp[0][0]=true;
      for(int j=1;j<=n;++j) 
         if(p[j]=='*') dp[0][j]=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-1][j]||dp[i][j-1];
          else dp[i][j]=(p[j]=='?'||s[i]==p[j])&&dp[i-1][j-1];
      return dp[m][n];
    }
};

 五、正则表达式匹配（重点）

. - 力扣（LeetCode）

class Solution {
public:
    bool isMatch(string s, string p) {
       //p中0-j的子串能否匹配s中0-i的子串
       int m=s.size(),n=p.size();
       s=" "+s,p=" "+p;//控制下标的映射
       vector<vector<bool>> dp(m+1,vector<bool>(n+1));
       //如果是  (p[j]=="."||p[j]==s[i])&&dp[i-1][j-1]
       //如果是 * 取决于p[j-1]   p[j-1]='.' 匹配空 dp[i][j-2]  匹配1个 dp[i-1][j-2]……
       //所以dp[i][j]=dp[i][j-2]||dp[i-1][j-2]||dp[i-2][j-2]……
       //数学推导 dp[i-1][j]=dp[i-1][j-2]||dp[i-2][j-2]……  
       //dp[i][j]=dp[i][j-2]||dp[i-1][j] 
       //如果p[j-1]==s[i] 
       //初始化
       dp[0][0]=true;
       for(int j=2;j<=n;j+=2) 
         if(p[j]=='*') dp[0][j]=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]=='.'||p[j]==s[i])&&dp[i-1][j-1];
          return dp[m][n];
    }
};

六、交错字符串

. - 力扣（LeetCode）

预处理：在s1、s2、s3前面加上“ ”

算法原理：

1、状态表示（经验+题目要求）

dp[i][j]表示：s1字符串的[1,i]区间和s2字符串的[1,j]区间的字符串能否拼凑成s3[1,i+j]子串

 2、状态转移方程

dp[i][j]:  （从最后一个位置）

dp[i][j]=    s1[i]==s3[i+j]&&dp[i-1][j] ||s2[j]==s3[i+j]&&dp[i][j-1]

3、初始化

引入空串去思考：

当s1和s2均为空串时，s3也为空串，所以是true

当s1是空串，s2不是空串时，s3取决于s2 所以如果第一行一直是s2[j]==s3[j]就是true，一旦有一个不满足，就跳出循环。

当s2是空串，s1不是空串时，s3取决于s1 所以如果第一列一直是s1[i]==s3[i]就是true，一旦有一个不满足，就跳出循环。

所以需要按照上面的规则对第一行和第一列进行相关的初始化。

4、填表顺序

从上往下填每一行

每一行从左往右填

5、返回值

dp[m][n]

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;
         //dp[i][j]表示s1 1-i s2 1-j 能否组成 s3 1-i+j
         vector<vector<bool>> dp(m+1,vector<bool>(n+1));
         //先初始化第一列  此时s2是空串
         dp[0][0]=true;
         for(int i=1;i<=m;++i) 
           if(s1[i]==s3[i]) dp[i][0]=true;
           else break;  
        //初始化第一行 s1是空串
        for(int j=1;j<=n;++j)
          if(s2[j]==s3[j]) dp[0][j]=true;
          else break;

          //开始填表 讨论最后一个位置  s1[i]==s[j]
          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];
    }
};

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

. - 力扣（LeetCode）

 预处理：要求删除序列的最小ascii值，删除之后剩下的序列是一样的，并且总ascii值是不变的，所以我们可以运用正难则反的思路。

将问题转化为：求两个字符串所有最长公共子序列中的ascii码值的最大和

算法原理：

1、状态表示（经验+题目要求）

dp[i][j]表示：s1字符串的[0,i]区间和s2字符串的[0,j]区间的所有子序列里，公共子序列最大的ascii码和

 2、状态转移方程

dp[i][j]:  （从最后一个位置）

s1[i]==s2[j]——dp[i-1][j-1]+s1[i]  

s1[i]!=s2[j]——max(dp[i-1][j],dp[i][j-1])

3、初始化

引入空串去思考：

都初始化为0即可

4、填表顺序

从上往下填每一行

每一行从左往右填

5、返回值

sum-2*dp[m][n]  （sum为两个字符串的ascii码值总和）

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));
       //正难则反 找两个字符串的最小ascii删除和可以等价于
       //找两个字符串的ascii总值-两个字符串的最长公共子序列的ascii值
       //dp[i][j] s1 0-i 以及s2 0-j 所有子序列中最长公共子序列的ascii值总和
       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];
          else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
         int sum=0;
         for(char&ch:s1) sum+=ch;
         for(char&ch:s2) sum+=ch;
         return sum-2*dp[m][n];
    }
};

八、最长重复子数组

. - 力扣（LeetCode）

 子数组最大的特点就是必须连续！！

算法原理：

1、状态表示（经验+题目要求）

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

 2、状态转移方程

dp[i][j]:  （从最后一个位置）

nums1[i]!=nums2[j]——>0

nums1[i]==nums2[j]——>dp[i-1][j-1]+1

3、初始化

都初始化为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));
         //dp[i][j]表示 nums1以i位置结尾 nums2以j位置结尾的最长公共子数组长度
         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.mfbz.cn/a/708560.html

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

相关文章

jenkins使用注意问题

jenkins使用注意问题

1.在编写流水线时并不知道当前处在哪个目录&#xff0c;导致名使用不当&#xff0c;以及文件位置不清楚 流水线任务默认路径是&#xff0c;test4_mvn为jenkins任务名 [Pipeline] sh (hide)pwd /var/jenkins_home/workspace/test4_mvn maven任务也是&#xff0c;看来是一样的…
阅读更多...
【Linux】Linux环境基础开发工具_6

【Linux】Linux环境基础开发工具_6

文章目录 四、Linux环境基础开发工具gdb 未完待续 四、Linux环境基础开发工具 gdb 我们已经可以写代码了&#xff0c;也能够执行代码了&#xff0c;但是代码错了该如何调试呢&#xff1f;Linux中可以使用 gdb 工具进行调试。 我们写一个简单的程序&#xff1a; 但是我们尝试…
阅读更多...
微信小程序毕业设计-实验室管理系统项目开发实战(附源码+论文)

微信小程序毕业设计-实验室管理系统项目开发实战(附源码+论文)

大家好&#xff01;我是程序猿老A&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。 &#x1f49e;当前专栏&#xff1a;微信小程序毕业设计 精彩专栏推荐&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb; &#x1f380; Python毕业设计…
阅读更多...
智慧工地：构筑未来建筑的智能脉络

智慧工地：构筑未来建筑的智能脉络

在科技日新月异的今天&#xff0c;智慧城市的建设已不再局限于城市生活的方方面面&#xff0c;而是深入到了城市发展的每一个细胞——工地。本文旨在深度剖析智慧工地的核心价值、关键技术及对建筑业转型升级的深远影响。 一、智慧工地&#xff1a;定义与愿景 智慧工地是指运…
阅读更多...
【智能家居控制系统项目】一、项目系统镜像烧录与系统登录

【智能家居控制系统项目】一、项目系统镜像烧录与系统登录

前言 完成本章节将可以获得本项目的系统UI界面功能。本章节主要介绍如何烧录项目系统镜像以及进入系统。配套的视频介绍可以点击跳转到智能家居项目复刻配套视频 1.系统功能页面介绍 完成本章全部步骤&#xff0c;我们将可使用以下项目系统功能界面。 1.1 家居总览界面 主界面…
阅读更多...
Zynq学习笔记--AXI4-Stream到视频输出IP是如何工作的？

Zynq学习笔记--AXI4-Stream到视频输出IP是如何工作的？

目录 1. 简介 2. 原理详解 2.1 示例工程 2.2 AXI4-Stream to Video Out 3. Master/Slave Timing Mode 3.1 Slave Timing Mode 3.2 Master Timing Mode 4. 总结 1. 简介 本文主要介绍了 AXI4-Stream 到视频输出 的内容。其中&#xff0c;示例工程展示了一个具体的设计&…
阅读更多...
八爪鱼现金流-023-独具特色的加密解决方案

八爪鱼现金流-023-独具特色的加密解决方案

大家一起来记账。 八爪鱼现金流。 独具特色的加密解决方案。金额数据加密后存储到数据库。 保证数据私密性。欢迎试用。 八爪鱼现金流。 点击【八爪鱼现金流-022-mybatis插件加密和国密SM4算法】文章查看详情。
阅读更多...
MySQL从入门到高级 --- 15.优化 16.pymysql

MySQL从入门到高级 --- 15.优化 16.pymysql

文章目录 第十五章 && 第十六章&#xff1a;15.优化15.1 查询SQL执行效率15.2 定位低效率执行SQL15.3 explain分析执行计划 - 基本使用15.4 explain分析执行计划 - id15.5 explain分析执行计划 - select_type15.6 explain分析执行计划 - type15.7 explain分析执行计划 …
阅读更多...
实验室管理系统实用性体现在哪些方面？

实验室管理系统实用性体现在哪些方面？

随着技术的不断进步和应用的不断深入&#xff0c;在当今的检验检测行业中&#xff0c;实验室管理系统的实用性成为了保证质量检测工作正常有效开展的基础&#xff0c;其重要性不言而喻。而实验室信息管理系统&#xff08;LIMS&#xff09;实用性不仅体现在其对实验室日常运作的…
阅读更多...
项目实战--文档搜索引擎

项目实战--文档搜索引擎

在我们的学习过程中&#xff0c;会阅读很多的文档&#xff0c;例如jdk的API文档&#xff0c;但是在这样的大型文档中&#xff0c;如果没有搜索功能&#xff0c;我们是很难找到我们想查阅的内容的&#xff0c;于是我们可以实现一个搜索引擎来帮助我们阅读文档。 1. 实现思路 1…
阅读更多...
ESP32基础应用之esp32连接腾讯云并使用微信小程序控制的智能灯

ESP32基础应用之esp32连接腾讯云并使用微信小程序控制的智能灯

文章目录 1. 项目简介1.1 功能接收1.2 使用资源1.3 测试平台 2 腾讯云物联网开发平台3 esp32设备开发3.1 准备参考例程3.2 vscode平台创建测试工程3.3 修改工程 问题总结使用PowerShell命令行终端生成的二维码不能用 1. 项目简介 1.1 功能接收 实现腾讯云创建项目与设备&…
阅读更多...
09-Spark架构

09-Spark架构

相比MapReduce僵化的Map与Reduce分阶段计算&#xff0c;Spark计算框架更有弹性和灵活性&#xff0c;运行性能更佳。 1 Spark的计算阶段 MapReduce一个应用一次只运行一个map和一个reduceSpark可根据应用复杂度&#xff0c;分割成更多的计算阶段&#xff08;stage&#xff09;…
阅读更多...
怎么脚本ai创作？分享三个方法

怎么脚本ai创作？分享三个方法

怎么脚本ai创作&#xff1f;在数字化时代&#xff0c;AI技术正逐渐渗透到我们生活的方方面面&#xff0c;其中AI脚本创作软件的出现&#xff0c;极大地提高了创作效率&#xff0c;降低了创作门槛。今天&#xff0c;就为大家推荐三款备受好评的AI脚本创作软件&#xff0c;其中聪…
阅读更多...
React-Redux

React-Redux

什么是Redux&#xff1f; Redux是React最常用的集中状态管理工具&#xff0c;类似于Vue中的Pinia&#xff08;Vuex&#xff09;&#xff0c;可以独立于框架运行 作用&#xff1a;通过集中管理的方式管理应用的状态
阅读更多...
定个小目标之刷LeetCode热题（19）

定个小目标之刷LeetCode热题（19）

这是道简单题&#xff0c;直接用快慢指针&#xff0c;代码如下 public class Solution {public boolean hasCycle(ListNode head) {if (head null || head.next null) {return false;}ListNode slow head;ListNode fast head.next;while (slow ! fast) {//遇到null则retur…
阅读更多...
java原子变量

java原子变量

在Java中&#xff0c;原子变量是一种特殊的变量&#xff0c;它们提供了一种不需要显式加锁的情况下进行线程安全的操作。Java.util.concurrent.atomic包提供了原子变量类&#xff0c;如AtomicInteger&#xff0c;AtomicLong等&#xff0c;它们利用底层硬件的原子操作来保证线程…
阅读更多...
华三HCL模拟器安装及华三防火墙配置

华三HCL模拟器安装及华三防火墙配置

0、前言 最近跟模拟器杠上了&#xff0c;主要是需要运行防火墙&#xff0c;目前已经成功模拟出华为、山石防火墙&#xff0c;而且模拟出来的设备能与物理网络环境进行互联。现在我又盯上华三防火墙了。 首先下载模拟器&#xff1a; 下载地址&#xff1a;H3C网络设备模拟器官方免…
阅读更多...
小程序 UI 风格，清新脱俗

小程序 UI 风格，清新脱俗

小程序 UI 风格&#xff0c;清新脱俗
阅读更多...
电脑文件msvcr120.dll丢失怎样修复？具体的msvcr120.dll修复方法分享

电脑文件msvcr120.dll丢失怎样修复？具体的msvcr120.dll修复方法分享

电脑文件msvcr120.dll丢失是一种比较常见的现象&#xff0c;只要是经常使用电脑的人&#xff0c;那么遇到msvcr120.dll丢失的次数就越多&#xff0c;今天主要来给大家聊一下msvcr120.dll丢失的各种解决方法。 一.电脑文件msvcr120.dll msvcr120.dl是由Microsoft提供的关键系统…
阅读更多...
vscode中模糊搜索和替换

vscode中模糊搜索和替换

文章目录 调出搜索&#xff08;快捷键&#xff09;使用正则&#xff08;快捷键&#xff09;替换&#xff08;快捷键&#xff09;案例假设给定文本如下目标1&#xff1a;查找所有函数名目标2&#xff1a;替换所有函数名为hello目标3&#xff1a;给url增加查询字符串参数 调出搜索…
阅读更多...
最新文章

Copyright @ 2022~2023