专题七：两个数组的 dp （含字符串数组）

置顶 于 2024-12-23 22:14:38 发布
阅读量834 收藏 38
点赞数 44
分类专栏： 动态规划算法 文章标签： 算法 动态规划 推荐算法 leetcode
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/AAlykk/article/details/144595047
版权

> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。

> 目标：了解什么是记忆化搜索，并且掌握记忆化搜索算法。

> 毒鸡汤：有些事情，总是不明白，所以我不会坚持。早安!

> 专栏选自：动态规划算法_დ旧言~的博客-CSDN博客

> 望小伙伴们点赞👍收藏✨加关注哟💕💕

一、算法讲解

动态规划（Dynamic Programming）算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法：

  • 动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
  • 与分治法不同的是，适合于用动态规划求解的问题，经分解得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上）。

【Tips】动态规划算法解决问题的分类：

  • 计数：有多少种方式走到右下角 / 有多少种方法选出k个数使得和是 sum。
  • 求最大值/最小值：从左上角走到右下角路径的最大数字和最长上升子序列长度。
  • 求存在性：取石子游戏，先手是否必胜 / 能不能取出 k 个数字使得和是 sum。

【Tips】动态规划dp算法一般步骤：

  1. 确定状态表示（dp[ i ] 的含义是什么，来源：1、题目要求；2、经验+题目要求；3、分析问题时发现重复子问题）
  2. 状态转移方程（可求得 dp[ i ] 的数学公式，来源：题目要求+状态表示）
  3. 初始化（dp 表中特别的初始值，保证填 dp 表时不会越界，来源：题目要求+状态表示）
  4. 填表顺序（根据状态转移方程修改 dp[ i ] 的方式，来源：题目要求+状态表示）
  5. 返回值（题目求解的结果，来源：题目要求+状态表示）

二、算法习题

2.1 第一题

题目链接：1143. 最长公共子序列 - 力扣（LeetCode）

题目描述：

算法思路：

1. 状态表⽰：

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

2. 状态转移⽅程：

对于 dp[i][j] ，我们可以根据 s1[i] 与 s2[j] 的字符分情况讨论：

  1. 两个字符相同， s1[i] = s2[j] ：那么最⻓公共⼦序列就在 s1 的 [0, i - 1] 以及 s2 的 [0, j - 1] 区间上找到⼀个最⻓的，然后再加上 s1[i] 即可。因此dp[i][j] = dp[i - 1][j - 1] + 1 ；
  2. 两个字符不相同， s1[i] != s2[j] ：那么最⻓公共⼦序列⼀定不会同时以 s1[i]和 s2[j] 结尾。那么我们找最⻓公共⼦序列时，有下⾯三种策略：

• 去 s1 的 [0, i - 1] 以及 s2 的 [0, j] 区间内找：此时最⼤⻓度为 dp[i- 1][j] ；
• 去 s1 的 [0, i] 以及 s2 的 [0, j - 1] 区间内找：此时最⼤⻓度为 dp[i ][j - 1] ；
• 去 s1 的 [0, i - 1] 以及 s2 的 [0, j - 1] 区间内找：此时最⼤⻓度为dp[i - 1][j - 1] 。

我们要三者的最⼤值即可。但是我们细细观察会发现，第三种包含在第⼀种和第⼆种情况⾥
⾯，但是我们求的是最⼤值，并不影响最终结果。因此只需求前两种情况下的最⼤值即可。

综上，状态转移⽅程为：

  • if(s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1] + 1 ;
  • if(s1[i] != s2[j]) dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) 。

3. 初始化：

  1. 「空串」是有研究意义的，因此我们将原始 dp 表的规模多加上⼀⾏和⼀列，表⽰空串。
  2. 引⼊空串后，⼤⼤的⽅便我们的初始化。
  3. 但也要注意「下标的映射关系」，以及⾥⾯的值要「保证后续填表是正确的」。

当 s1 为空时，没有⻓度，同理 s2 也是。因此第⼀⾏和第⼀列⾥⾯的值初始化为 0 即可保证后续填表是正确的。

4. 填表顺序：

根据「状态转移⽅程」得：从上往下填写每⼀⾏，每⼀⾏从左往右。

5. 返回值：

根据「状态表⽰」得：返回 dp[m][n] 。

代码呈现：

class Solution {
public:
    int longestCommonSubsequence(string s1, string s2) 
    {
        int m = s1.size(), n = s2.size();
        s1 = " " + s1, s2 = " " + s2;                      // 处理下标映射关系
        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] == s2[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];
    }
};

2.2 第二题

题目链接：1035. 不相交的线 - 力扣（LeetCode）

题目描述：

算法思路：

如果要保证两条直线不相交，那么我们「下⼀个连线」必须在「上⼀个连线」对应的两个元素「后⾯」寻找相同的元素。这不就转化成「最⻓公共⼦序列」的模型了嘛。那就是在这两个数组中寻找「最⻓的公共⼦序列」。

代码呈现：

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) 
    {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        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];
    }
};

2.3 第三题

题目链接：115. 不同的子序列 - 力扣（LeetCode）

题目描述：

算法思路：

1. 状态表⽰：

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

2. 状态转移⽅程：

⽼规矩，根据「最后⼀个位置」的元素，结合题⽬要求，分情况讨论：

i. 当 t[i] == s[j] 的时候，此时的⼦序列有两种选择：

  • ⼀种选择是：⼦序列选择 s[j] 作为结尾，此时相当于在状态 dp[i - 1][j - 1]中的所有符合要求的⼦序列的后⾯，再加上⼀个字符 s[j] （请⼤家结合状态表，好好理解这句话），此时 dp[i][j] = dp[i - 1][j - 1] ；
  • 另⼀种选择是：我就是任性，我就不选择 s[j] 作为结尾。此时相当于选择了状态dp[i][j - 1] 中所有符合要求的⼦序列。我们也可以理解为继承了上个状态⾥⾯的求得的⼦序列。此时 dp[i][j] = dp[i][j - 1] ；

两种情况加起来，就是 t[i] == s[j] 时的结果。

ii. 当 t[i] != s[j] 的时候，此时的⼦序列只能从 dp[i][j - 1] 中选择所有符合要求的⼦序列。只能继承上个状态⾥⾯求得的⼦序列， dp[i][j] = dp[i][j - 1] ；

综上所述，状态转移⽅程为：

  • 所有情况下都可以继承上⼀次的结果： dp[i][j] = dp[i][j - 1] ；
  • 当 t[i] == s[j] 时，可以多选择⼀种情况： dp[i][j] += dp[i - 1][j - 1]

3. 初始化：

  1. 「空串」是有研究意义的，因此我们将原始 dp 表的规模多加上⼀⾏和⼀列，表⽰空串。
  2. 引⼊空串后，⼤⼤的⽅便我们的初始化。
  3. 但也要注意「下标的映射关系」，以及⾥⾯的值要「保证后续填表是正确的」。当 s 为空时， t 的⼦串中有⼀个空串和它⼀样，因此初始化第⼀⾏全部为 1 。

4. 填表顺序：

「从上往下」填每⼀⾏，每⼀⾏「从左往右」。

5. 返回值：

根据「状态表⽰」，返回 dp[m][n] 的值。

代码呈现：

class Solution {
public:
    int numDistinct(string s, string t) 
    {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int m = t.size(), n = s.size();
        vector<vector<double>> dp(m + 1, vector<double>(n + 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];
    }
};

2.4 第四题

题目链接：44. 通配符匹配 - 力扣（LeetCode）

题目描述：

算法思路：

1. 状态表⽰：

dp[i][j] 表⽰： p 字符串 [0, j] 区间内的⼦串能否匹配字符串 s 的 [0, i] 区间内的⼦串。

2. 状态转移⽅程：

⽼规矩，根据最后⼀个位置的元素，结合题⽬要求，分情况讨论：

 i. 当 s[i] == p[j] 或 p[j] == '?' 的时候，此时两个字符串匹配上了当前的⼀个字符，只能从 dp[i - 1][j - 1] 中看当前字符前⾯的两个⼦串是否匹配。只能继承上个状态中的匹配结果， dp[i][j] = dp[i][j - 1] 

ii. 当 p[j] == '*' 的时候，此时匹配策略有两种选择： 

  • ⼀种选择是： * 匹配空字符串，此时相当于它匹配了⼀个寂寞，直接继承状态 dp[i][j - 1] ，此时 dp[i][j] = dp[i][j - 1] ；
  • 另⼀种选择是： * 向前匹配 1 ~ n 个字符，直⾄匹配上整个 s1 串。此时相当于从 dp[k][j - 1] (0 <= k <= i) 中所有匹配情况中，选择性继承可以成功的情况。此时 dp[i][j] = dp[k][j - 1] (0 <= k <= i) ；

iii. 当 p[j] 不是特殊字符，且不与 s[i] 相等时，⽆法匹配。

综上所述，状态转移⽅程为：

  • 当 s[i] == p[j] 或 p[j] == '?' 时： dp[i][j] = dp[i][j - 1] ；
  • 当 p[j] == '*' 时，有多种情况需要讨论： dp[i][j] = dp[k][j - 1] (0 <=k <= i) ；

3. 初始化：

由于 dp 数组的值设置为是否匹配，为了不与答案值混淆，我们需要将整个数组初始化为false 。
由于需要⽤到前⼀⾏和前⼀列的状态，我们初始化第⼀⾏、第⼀列即可。

  • dp[0][0] 表⽰两个空串能否匹配，答案是显然的， 初始化为 true 。
  • 第⼀⾏表⽰ s 是⼀个空串， p 串和空串只有⼀种匹配可能，即 p 串表⽰为 "***" ，此时也相当于空串匹配上空串。所以，我们可以遍历 p 串，把所有前导为 "*" 的 p ⼦串和空串的 dp 值设为 true 。
  • 第⼀列表⽰ p 是⼀个空串，不可能匹配上 s 串，跟随数组初始化即可。 

4. 填表顺序：

从上往下填每⼀⾏，每⼀⾏从左往右。

5. 返回值：

根据状态表⽰，返回 dp[m][n] 的值。

代码呈现：

class Solution {
public:
    bool isMatch(string s, string p) 
    {
        int m = s.size(), n = p.size();
        s = " " + s, p = " " + p;
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1)); // 1. 创建 dp 表
        dp[0][0] = true;                                     // 2. 初始化
        for (int j = 1; j <= n; j++)
            if (p[j] == '*')
                dp[0][j] = true;
            else
                break;
        // 3. 填表
        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];
            }
        }
        // 4. 返回值
        return dp[m][n];
    }
};

2.5 第五题

题目链接：10. 正则表达式匹配 - 力扣（LeetCode）

题目描述：

  

算法思路：

1. 状态表⽰：

dp[i][j] 表⽰：字符串 p 的 [0, j] 区间和字符串 s 的 [0, i] 区间是否可以匹配。

2. 状态转移⽅程：

⽼规矩，根据最后⼀个位置的元素，结合题⽬要求，分情况讨论：

a. 当 s[i] == p[j] 或 p[j] == '.' 的时候，此时两个字符串匹配上了当前的⼀个字符，只能从 dp[i - 1][j - 1] 中看当前字符前⾯的两个⼦串是否匹配。只能继承上个状态中的匹配结果， dp[i][j] = dp[i - 1][j-1] ；

b. 当 p[j] == '*' 的时候，和上道题稍有不同的是，上道题 "*" 本⾝便可匹配 0 ~ n 个字符，但此题是要带着 p[j - 1] 的字符⼀起，匹配 0 ~ n 个和 p[j - 1] 相同的字符。此时，匹配策略有两种选择：

  • ⼀种选择是： p[j - 1]* 匹配空字符串，此时相当于这两个字符都匹配了⼀个寂寞，直接继承状态 dp[i][j - 2] ，此时 dp[i][j] = dp[i][j - 2] ；
  • 另⼀种选择是： p[j - 1]* 向前匹配 1 ~ n 个字符，直⾄匹配上整个 s1 串。此时相当于从 dp[k][j - 2] (0 < k <= i) 中所有匹配情况中，选择性继承可以成功的情况。此时 dp[i][j] = dp[k][j - 2] (0 < k <= i 且 s[k]~s[i] = p[j- 1]) ；

c. 当 p[j] 不是特殊字符，且不与 s[i] 相等时，⽆法匹配。

综上所述，状态转移⽅程为：

  • 当 s[i] == p[j] 或 p[j] == '.' 时： dp[i][j] = dp[i][j - 1] 
  • 当 p[j] == '*' 时，有多种情况需要讨论： dp[i][j] = dp[i][j - 2] ；dp[i][j] = dp[k][j - 1] (0 <= k <= i) 

3. 初始化：

由于 dp 数组的值设置为是否匹配，为了不与答案值混淆，我们需要将整个数组初始化为false 。
由于需要⽤到前⼀⾏和前⼀列的状态，我们初始化第⼀⾏、第⼀列即可。

dp[0][0] 表⽰两个空串能否匹配，答案是显然的， 初始化为 true 。

第⼀⾏表⽰ s 是⼀个空串， p 串和空串只有⼀种匹配可能，即 p 串全部字符表⽰为 "任⼀字符+*"，此时也相当于空串匹配上空串。所以，我们可以遍历 p 串，把所有前导为 "任⼀字符 + *"的 p ⼦串和空串的 dp 值设为 true 。

第⼀列表⽰ p 是⼀个空串，不可能匹配上 s 串，跟随数组初始化即可。

4. 填表顺序：

从上往下填每⼀⾏，每⼀⾏从左往右。

5. 返回值：

根据状态表⽰，返回 dp[m][n] 的值。

代码呈现：

class Solution {
public:
    bool isMatch(string s, string p) 
    {
        int m = s.size(), n = p.size();
        s = ' ' + s, p = ' ' + p;
        // 1. 创建 dp 表
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
        // 2. 初始化
        dp[0][0] = true;
        for (int j = 2; j <= n; j += 2)
            if (p[j] == '*')
                dp[0][j] = true;
            else
                break;
        // 3. 填表
        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] == s[i] || p[j] == '.') && dp[i - 1][j - 1];
            }
        }
        // 4. 返回值
        return dp[m][n];
    }
};

2.6 第六题

题目链接：97. 交错字符串 - 力扣（LeetCode）

题目描述：

  

算法思路：

对于两个字符串之间的 dp 问题，我们⼀般的思考⽅式如下：

  1. 选取第⼀个字符串的 [0, i] 区间以及第⼆个字符串的 [0, j] 区间当成研究对象，结合题⽬的要求来定义「状态表⽰」；
  2. 然后根据两个区间上「最后⼀个位置的字符」，来进⾏「分类讨论」，从⽽确定「状态转移⽅程」。

这道题⾥⾯空串是有研究意义的，因此我们先预处理⼀下原始字符串，前⾯统⼀加上⼀个占位符：

s1 = " " + s1, s2 = " " + s2, s3 = " " + s3 。

1. 状态表⽰：

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

2. 状态转移⽅程：

先分析⼀下题⽬，题⽬中交错后的字符串为 s1 + t1 + s2 + t2 + s3 + t3...... ，看似⼀个 s ⼀个 t 。实际上 s1 能够拆分成更⼩的⼀个字符，进⽽可以细化成 s1 + s2 +s3 + t1 + t2 + s4...... 。

  1. 当 s3[i + j] = s1[i] 的时候，说明交错后的字符串的最后⼀个字符和 s1 的最后⼀个字符匹配了。那么整个字符串能否交错组成，变成：s1 中 [1, i - 1] 区间上的字符串以及 s2 中 [1, j] 区间上的字符串，能够交错形成 s3 中 [1, i + j - 1] 区间上的字符串，也就是 dp[i - 1][j] ；此时 dp[i][j] = dp[i - 1][j]
  2. 当 s3[i + j] = s2[j] 的时候，说明交错后的字符串的最后⼀个字符和 s2 的最后⼀个字符匹配了。那么整个字符串能否交错组成，变成：s1 中 [1, i] 区间上的字符串以及 s2 中 [1, j - 1] 区间上的字符串，能够交错形成 s3 中 [1, i + j - 1] 区间上的字符串，也就是 dp[i][j - 1] ；
  3. 当两者的末尾都不等于 s3 最后⼀个位置的字符时，说明不可能是两者的交错字符串。上述三种情况下，只要有⼀个情况下能够交错组成⽬标串，就可以返回 true 。因此，我们可以定义状态转移为：

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

只要有⼀个成⽴，结果就是 true 。

3. 初始化：

◦ 第⼀个位置：

dp[0][0] = true ，因为空串 + 空串能够构成⼀个空串。

◦ 第⼀⾏：

第⼀⾏表⽰ s1 是⼀个空串，我们只⽤考虑 s2 即可。因此状态转移之和 s2 有关：dp[0][j] = s2[j - 1] == s3[j - 1] && dp[0][j - 1] ， j 从 1 到 n（ n 为 s2 的⻓度）

◦ 第⼀列：

第⼀列表⽰ s2 是⼀个空串，我们只⽤考虑 s1 即可。因此状态转移之和 s1 有关：dp[i][0] = s1[i -1] == s3[i - 1] && dp[i - 1][0] ， i 从 1 到 m（ m 为 s1 的⻓度）

4. 填表顺序：

根据「状态转移」，我们需要「从上往下」填每⼀⾏，每⼀⾏「从左往右」。

5. 返回值：

根据「状态表⽰」，我们需要返回 dp[m][n] 的值。

代码呈现：

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) 
    {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        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 j = 1; j <= n; j++) // 初始化第⼀⾏
            if (s2[j] == s3[j])
                dp[0][j] = 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++)
                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];
    }
};

2.7 第七题

题目链接：712. 两个字符串的最小ASCII删除和 - 力扣（LeetCode）

题目描述：

  

算法思路：

正难则反：求两个字符串的最⼩ ASCII 删除和，其实就是找到两个字符串中所有的公共⼦序列⾥⾯， ASCII 最⼤和。

1. 状态表⽰：

dp[i][j] 表⽰： s1 的 [0, i] 区间以及 s2 的 [0, j] 区间内的所有的⼦序列中，公共⼦序列的 ASCII 最⼤和。

2. 状态转移⽅程：

对于 dp[i][j] 根据「最后⼀个位置」的元素，结合题⽬要求，分情况讨论：

  1. 当 s1[i] == s2[j] 时：应该先在 s1 的 [0, i - 1] 区间以及 s2 的 [0, j- 1] 区间内找⼀个公共⼦序列最⼤和，然后在它们后⾯加上⼀个 s1[i] 字符即可。此时 dp[i][j] = dp[i - 1][j - 1] + s1[i] ；
  2. 当 s1[i] != s2[ j] 时：公共⼦序列的最⼤和会有三种可能：

• s1 的 [0, i - 1] 区间以及 s2 的 [0, j] 区间内：此时 dp[i][j] = dp[i - 1][j] ；
• s1 的 [0, i] 区间以及 s2 的 [0, j - 1] 区间内：此时 dp[i][j] = dp[i][j - 1] ；
• s1 的 [0, i - 1] 区间以及 s2 的 [0, j - 1] 区间内：此时 dp[i][j] = dp[i - 1][j - 1] 。

综上所述，状态转移⽅程为：

  • 当 s1[i - 1] == s2[j - 1] 时， dp[i][j] = dp[i - 1][j - 1] + s1[i] ；
  • 当 s1[i - 1] != s2[j - 1] 时， dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

3. 初始化：

  1. 「空串」是有研究意义的，因此我们将原始 dp 表的规模多加上⼀⾏和⼀列，表⽰空串。
  2. 引⼊空串后，⼤⼤的「⽅便我们的初始化」。
  3.  但也要注意「下标的映射」关系，以及⾥⾯的值要保证「后续填表是正确的」。
  4. 当 s1 为空时，没有⻓度，同理 s2 也是。因此第⼀⾏和第⼀列⾥⾯的值初始化为 0 即可保证后续填表是正确的。

4. 填表顺序：

「从上往下」填每⼀⾏，每⼀⾏「从左往右」。

5. 返回值：

根据「状态表⽰」，我们不能直接返回 dp 表⾥⾯的某个值：

  1. 先找到 dp[m][n] ，也是最⼤公共 ASCII 和；
  2. 统计两个字符串的 ASCII 码和 s u m；
  3. 返回 sum - 2 * dp[m][n] 。

代码呈现：

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) 
    {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        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++) 
            {
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
                if (s1[i - 1] == s2[j - 1])
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + s1[i - 1]);
            }
        int sum = 0; // 统计元素和
        for (auto s : s1)
            sum += s;
        for (auto s : s2)
            sum += s;
        return sum - dp[m][n] - dp[m][n];
    }
};

2.8 第八题

题目链接：718. 最长重复子数组 - 力扣（LeetCode）

题目描述：

  

算法思路：

⼦数组是数组中「连续」的⼀段，我们习惯上「以某⼀个位置为结尾」来研究。由于是两个数组，因此我们可以尝试：以第⼀个数组的 i 位置为结尾以及第⼆个数组的 j 位置为结尾来解决问题。

1. 状态表⽰：

dp[i][j] 表⽰「以第⼀个数组的 i 位置为结尾」，以及「第⼆个数组的 j 位置为结尾」公共的 、⻓度最⻓的「⼦数组」的⻓度。

2. 状态转移⽅程：

对于 dp[i][j] ，当 nums1[i] == nums2[j] 的时候，才有意义，此时最⻓重复⼦数组的⻓度应该等于 1 加上除去最后⼀个位置时，以 i - 1, j - 1 为结尾的最⻓重复⼦数组的⻓度。因此，状态转移⽅为： dp[i][j] = 1 + dp[i - 1][j - 1]

3. 初始化：

为了处理「越界」的情况，我们可以添加⼀⾏和⼀列， dp 数组的下标从 1 开始，这样就⽆需初始化。第⼀⾏表⽰第⼀个数组为空，此时没有重复⼦数组，因此⾥⾯的值设置成 0 即可；第⼀列也是同理。

4. 填表顺序：

根据「状态转移」，我们需要「从上往下」填每⼀⾏，每⼀⾏「从左往右」。

5. 返回值：

根据「状态表⽰」，我们需要返回 dp 表⾥⾯的「最⼤值」。

代码呈现：

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) 
    {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        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;
    }
};

三、结束语 

今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。

​​ 

评论 18
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值