devbox
Monodyee
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

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

作者：Monodyee | 2024-06-15 23:43:43

赞

踩

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

目录

leetcode题目

一、最长公共子序列

二、不相交的线

三、不同的子序列

四、通配符匹配

五、正则表达式匹配

六、交错字符串

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

八、最长重复子数组

leetcode题目

一、最长公共子序列

1143. 最长公共子序列 - 力扣（LeetCode）icon-default.png?t=N7T8https://leetcode.cn/problems/longest-common-subsequence/1.题目解析

找两个字符串的最长公共子序列的长度

2.算法分析

1.状态表示

经验+题目要求: 选取第一个字符串[0, i] 区间以及第二个字符串[0, j] 区间作为研究对象

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

2.状态转移方程

根据最后一个位置的情况，分情况讨论

3.初始化

在原始dp表上添加一行一列,  第一行表示第一个字符串为空，第二行表示第二个字符串为空，根据实际含义，将第一行第一列都填成0，填表就不会越界了并且后续填表是正确的，而我们可以在s1和s2前面都加'_', 这样dp表和原始字符串的下标就一一对应了

4.填表顺序

从上往下填表，每一行从左往右

5.返回值

dp[m][n]

3.算法代码

  1. class Solution {
  2. public:
  3.     int longestCommonSubsequence(string s1, string s2) 
  4.     {
  5.         int m = s1.size(), n = s2.size();
  6.         //1.创建dp表 + 初始化
  7.         vector<vector<int>> dp(m+1, vector<int>(n+1));
  8.         s1 = " " + s1, s2 = " " + s2; 
  9.         //2.填表
  10.         for(int i = 1; i <= m; i++)
  11.         {
  12.             for(int j = 1; j <= n; j++)
  13.             {
  14.                 if(s1[i] == s2[j])
  15.                     dp[i][j] = dp[i-1][j-1] + 1;
  16.                 else
  17.                     dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
  18.             }
  19.         }
  20.         //3.返回值
  21.         return dp[m][n];
  22.     }
  23. };

二、不相交的线

1035. 不相交的线 - 力扣（LeetCode）icon-default.png?t=N7T8https://leetcode.cn/problems/uncrossed-lines/1.题目解析

给定两个数组，要求将两个数组中相同的元素进行连线，但是不能相交，并且一个数字只能属于一个线， 求最多的线段个数

2.算法分析
本质和题目一是一样的，只是题目一是在两字符串中求最长公共子序列，而本题是在两个数组中秋最长公共子序列
解法和题目一是一模一样的~
只是本题直接在数组前加空格不太方便，可以用修改下标映射关系，让其一一对应即可
3.算法代码

  1. class Solution 
  2. {
  3. public:
  4.     int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2)
  5.     {
  6.         int m = nums1.size(), n = nums2.size();
  7.         //1.创建dp表 + 初始化
  8.         vector<vector<int>> dp(m+1, vector<int>(n+1));
  9.         //2.填表
  10.         for(int i = 1; i <= m; i++)
  11.         {
  12.             for(int j = 1; j <= n; j++)
  13.             {
  14.                 if(nums1[i-1] == nums2[j-1])
  15.                     dp[i][j] = dp[i-1][j-1] + 1;
  16.                 else
  17.                     dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
  18.             }
  19.         }
  20.         //3.返回值
  21.         return dp[m][n];
  22.     }
  23. };

三、不同的子序列

115. 不同的子序列 - 力扣（LeetCode）icon-default.png?t=N7T8https://leetcode.cn/problems/distinct-subsequences/

1.题目解析

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数

2.算法分析

1.状态表示

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

2.状态转移方程

3.初始化

dp表添加一行一列, t字符串和s字符串前加 "_"

第一行i位0， 表示t是空串，这种情况下无论s是啥样子，只要一个不选，就是空串，因此第一行全部初始化成1

第一列i为0， 表示s是空串，这种情况下只有当t是空串(dp[0][0])，才是1种情况，其余都是0

4.填表顺序

从上往下填表，每一行从左往右

5.返回值

dp[m][n]

3.算法代码

  1. class Solution {
  2. public:
  3.     int numDistinct(string s, string t) 
  4.     {
  5.         int m = t.size(), n = s.size();
  6.         s = " " + s, t = " " + t;
  7.         //1.创建dp表
  8.         vector<vector<int>> dp(m+1, vector<int>(n+1));
  9.         //2.初始化
  10.         for(int j = 0; j <= n; j++) 
  11.             dp[0][j] = 1;
  12.         //3.填表
  13.         for(int i = 1; i <= m; i++)
  14.         {
  15.             for(int j = 1; j <= n; j++)
  16.             {
  17.                 dp[i][j] += (dp[i][j-1] % (1000000000 + 7));
  18.                 if(t[i] == s[j])
  19.                     dp[i][j] += (dp[i-1][j-1] % (1000000000 + 7));
  20.             }
  21.         }
  22.         //4.返回值
  23.         return dp[m][n] % (1000000000 + 7);
  24.     }
  25. };

四、通配符匹配

44. 通配符匹配 - 力扣（LeetCode）icon-default.png?t=N7T8https://leetcode.cn/problems/wildcard-matching/1.题目解析

给定s串和p串，问p串是否能和s串完全匹配

匹配规则：

1.'?'可以匹配任意单个字符

2.'*'可以匹配任意字符序列(多个字符, 包括空字符串也能匹配)

3.其他字符一一对应即可

eg:   s = "abcdef"   p = "*a*f"

这两个字符串就是可以匹配的，让第二个字符串的'*'匹配空串，'a'匹配'a', '*'匹配"bcde", 'f'匹配'f'即可

2.算法分析

1.状态表示

dp[i][j]: p[0, j] 区间内的子串是否能匹配 s[0, i] 区间内的子串
2.状态转移方程

上图是根据最后一个位置的状态划分问题得到的状态转移方程，但显然p[j]=='*'时，还需要一层for循环求解, 因此时间复杂度是O(N^3),  因此我们可以进一步优化, 将p[j]=='*'时的状态转移方程用若干个有限的状态表示

3.初始化

添加一行一列

dp[0][0] = true, 因为两个空串是匹配的

第一行的其他元素: 

第一行是i = 0, 表示s串是空串，而p串不是空串，因此想要p串匹配s串，p串必须全为连续的'*'字符。 所以写一个for循环，j遍历，当p[j]是'*'时， dp表的该位置是true, 否则后续全为false

第一列的其他元素:

p串为空，s串不为空，无法匹配， 值为false

4.填表顺序

从上往下填表，每一行从左往右

5.返回值

dp[m][n]

3.算法代码

  1. class Solution {
  2. public:
  3.     bool isMatch(string s, string p) 
  4.     {
  5.         int m = s.size(), n = p.size();
  6.         s = "_" + s, p = "_" + p;
  7.         //1.创建dp表
  8.         vector<vector<bool>> dp(m+1, vector<bool>(n+1));
  9.         //2.初始化
  10.         dp[0][0] = true;
  11.         for(int j = 1; j <= n; j++)
  12.             if(p[j] == '*') dp[0][j] = true;
  13.             else break;
  14.         //3.填表
  15.         for(int i = 1; i <= m; i++)
  16.         {
  17.             for(int j = 1; j <= n; j++)
  18.             {
  19.                 if(p[j] == '*') 
  20.                     dp[i][j] = dp[i][j-1] || dp[i-1][j];
  21.                 else 
  22.                     dp[i][j] = (p[j] == '?' || s[i] == p[j]) && dp[i-1][j-1];
  23.             }
  24.         }
  25.         //4.返回值
  26.         return dp[m][n];
  27.     }
  28. };

五、正则表达式匹配

10. 正则表达式匹配 - 力扣（LeetCode）icon-default.png?t=N7T8https://leetcode.cn/problems/regular-expression-matching/1.题目解析

给定s串和p串，请你判断s串和p串是否能匹配

匹配规则:

1.'.'匹配任意单个字符

2.'*'要结合前面的一个字符来解析，比如"a*"可以表示空串，可以表示a, 可以表示aa, 可以表示aaa等等

3.'*'前面如果还是一个'*',  是无效的，因为无法被解析, 题目保证了不会出现这种情况

题目保证了字符串中只有小写字母和'.'与'*'

2.算法分析

1.状态表示

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

2.状态转移方程

3.初始化

添加一行一列

dp[0][0] = true, 因为两个空串是匹配的

第一行的其他元素: 

第一行是i = 0, 表示s串是空串，而p串不是空串，因此想要p串匹配s串: p串必须是:

_*_*_*的形式，假如第一个位置是1，也就是要求连续的偶数位置都是*, 此时才能匹配，当某一个偶数为不是*了，后续的dp值都是false

第一列的其他元素:

p串为空，s串不为空，无法匹配， 值为false

4.填表顺序

从上往下填表，每一行从左往右

5.返回值

dp[m][n]

3.算法代码

  1. class Solution {
  2. public:
  3.     bool isMatch(string s, string p) 
  4.     {
  5.         int m = s.size(), n = p.size();
  6.         s = "_" + s, p = "_" + p;
  7.         //1.创建dp表
  8.         vector<vector<bool>> dp(m+1, vector<bool>(n+1));
  9.         //2.初始化
  10.         dp[0][0] = true;
  11.         for(int j = 2; j <= n; j += 2)
  12.             if(p[j] == '*') dp[0][j] = true;
  13.             else break;
  14.         //3.填表
  15.         for(int i = 1; i <= m; i++)
  16.         {
  17.             for(int j = 1; j <= n; j++)
  18.             {
  19.                 if(p[j] == '*') 
  20.                     dp[i][j] = dp[i][j-2] || ((p[j-1] == '.' || p[j-1] == s[i]) && dp[i-1][j]);
  21.                 else 
  22.                     dp[i][j] = (p[j] == s[i] || p[j] == '.') && dp[i-1][j-1];
  23.             }
  24.         }
  25.         //4.返回值
  26.         return dp[m][n];
  27.     }
  28. };

六、交错字符串

97. 交错字符串 - 力扣（LeetCode）icon-default.png?t=N7T8https://leetcode.cn/problems/interleaving-string/1.题目解析

给定字符串s1, s2, s3, 判断s1和s2能否交错构成s3

2.算法分析

先预处理一下，将三个字符串的前面加上'_'

1.状态表示

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

2.状态转移方程

3.初始化

dp[0][0] = true, 表示两个空串可以拼接成空串

第一行的其余位置：

s1为空，s2不为空，所以当s2对应位置字符和s3对应位置字符相等时，就是true, 某个位置不相等，则后续的dp值都是false

第一列的其余位置：

s2为空，s1不为空，所以当s1对应位置字符和s3对应位置字符相等时，就是true, 某个位置不相等，则后续的dp值都是false

4.填表顺序

从上往下填表，每一行从左往右

5.返回值

dp[m][n]

3.算法代码

  1. class Solution {
  2. public:
  3.     bool isInterleave(string s1, string s2, string s3) 
  4.     {
  5.         //1.创建dp表
  6.         int m = s1.size(), n = s2.size();
  7.         if(m + n != s3.size()) return false; //s1长度+s2长度 != s3长度，直接返回false
  8.         s1 = " " + s1, s2 = " " + s2, s3 = " " + s3;
  9.         vector<vector<bool>> dp(m+1, vector<bool>(n+1));
  10.         //2.初始化dp表
  11.         dp[0][0] = true;
  12.         for(int j = 1; j <= n; j++)
  13.             if(s2[j] == s3[j]) dp[0][j] = true;
  14.             else break;
  15.         for(int i = 1; i <= m; i++)
  16.             if(s1[i] == s3[i]) dp[i][0] = true;
  17.             else break;
  18.         //3.填表
  19.         for(int i = 1; i <= m; i++)
  20.             for(int j = 1; j <= n; j++)
  21.                 dp[i][j] = (s1[i] == s3[i+j] && dp[i-1][j]) || (s2[j] == s3[i+j] && dp[i][j-1]);
  22.         //4.返回值
  23.         return dp[m][n];
  24.     }
  25. };

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

712. 两个字符串的最小ASCII删除和 - 力扣（LeetCode）icon-default.png?t=N7T8https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/description/1.题目解析

给定两个字符串，每个字符串都可以删除若干字符，删除之后使得两个字符串相等，求删除的字符的最小的ASCII值之和

2.算法分析

正难则反: 求两个字符串里面的所有公共子序列里面，ASCII值的最大和

1.状态表示

dp[i][j]: s1的 [0, i] 区间以及 s2的 [0, j] 区间内的所有子序列里，公共子序列的ASCII的最大和

2.状态转移方程

3.初始化

添加一行一列, 全都初始化0，因为任何一个字符串为空，公共子序列的ASCII之和都是空
4.填表顺序

从上往下填表，每一行从左往右

5.返回值

两个字符串的ASCII之和 - dp[m][n] * 2

3.算法代码

  1. class Solution {
  2. public:
  3.     int minimumDeleteSum(string s1, string s2) 
  4.     {
  5.         //1.创建dp表 + 初始化
  6.         int m = s1.size(), n = s2.size();
  7.         s1 = " " + s1, s2 = " " + s2;
  8.         vector<vector<int>> dp(m+1, vector<int>(n+1));
  9.         //2.填表
  10.         for(int i = 1; i <= m; i++)
  11.         {
  12.             for(int j = 1; j <= n; j++)
  13.             {
  14.                 dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
  15.                 if(s1[i] == s2[j])
  16.                     dp[i][j] = max(dp[i][j], dp[i-1][j-1] + s1[i]);
  17.             }
  18.         }
  19.         //3.返回值
  20.         int sum = 0;
  21.         for(int i = 1; i <= m; i++)
  22.             sum += s1[i];
  23.         for(int j = 1; j <= n; j++)
  24.             sum += s2[j];
  25.         return sum - dp[m][n] * 2;
  26.     }
  27. };

八、最长重复子数组

718. 最长重复子数组 - 力扣（LeetCode）icon-default.png?t=N7T8https://leetcode.cn/problems/maximum-length-of-repeated-subarray/1.题目解析

找出两个数组中的最长重复子数组， 返回长度

2.算法分析

1.状态表示

dp[i][j]: nums1中以 i 位置元素为结尾的所有子数组以及nums2中以 j 位置元素为结尾的所有子数组中，最长重复子数组的长度

2.状态转移方程

3.初始化

添加一行一列,全部初始化成0(因为任何一个子数组为空，最长重复子数组长度就是0)

4.填表顺序

从上往下填表

5.返回值

dp表的最大值

3.算法代码
 

  1. class Solution {
  2. public:
  3.     int findLength(vector<int>& nums1, vector<int>& nums2) 
  4.     {
  5.         //1.创建dp表
  6.         int m = nums1.size(), n = nums2.size();
  7.         vector<vector<int>> dp(m+1, vector<int>(n+1));
  8.         //2.填表
  9.         int ret = 0;
  10.         for(int i = 1; i <= m; i++)
  11.         {
  12.             for(int j = 1; j <= n; j++)
  13.             {
  14.                 if(nums1[i-1] == nums2[j-1])
  15.                     dp[i][j] = dp[i-1][j-1] + 1;
  16.                 ret = max(ret, dp[i][j]);
  17.             }
  18.         }
  19.         //3.返回值
  20.         return ret;
  21.     }
  22. };

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/724265
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号