LeetCodeCampsDay45动态规划part12

下面几个子序列的题目都需要使用二维dp，而且关于两个字符串删除问题

并且都需要扩展dp的大小为dp(len(t1)+1, len(t2)+1)，第一行、第一列往往需要填充

所有涉及到两个字符串的dp问题，都有相似的状态转移过程

其中text1[i - 1] == text2[j - 1]，dp[i][j]

以及text1[i - 1] != text2[j - 1]，dp[i][j]

而dp[i][j]只能从dp[i - 1][j - 1]、dp[i - 1][j]、dp[i][j - 1]三种状态转移过来，只要能找到不同条件下状态转移的过程就好解决了

115. 不同的子序列

https://leetcode.cn/problems/distinct-subsequences/

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

测试用例保证结果在 32 位有符号整数范围内。

示例 1：

1
2
3
4
5
6
7
输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

示例 2：

1
2
3
4
5
6
7
8
9
输入：s = "babgbag", t = "bag"
输出：5
解释：
如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
babgbag
babgbag
babgbag
babgbag
babgbag

提示：

  • 1 <= s.length, t.length <= 1000
  • s 和 t 由英文字母组成

动态规划代码

  1. dp下标与含义

dp[i][j]表示s[i - 1]和t[j - 1]，dp[i][j]出现的个数

  1. 递推公式

这一类两个字符串的问题，一般都要按相等与不相等两种情况进行讨论；

并且，一定要注意，哪个字符串是被删除对象，被删除对象往往放在纵向遍历；

当s[i - 1] 与 t[j - 1]相等时，dp[i][j]可以有两部分组成。

一部分是用s[i - 1]来匹配，那么个数为dp[i - 1][j - 1]。即不需要考虑当前s子串和t子串的最后一位字母，所以只需要 dp[i-1][j-1]。

一部分是不用s[i - 1]来匹配，个数为dp[i - 1][j]。

例如： s：bagg 和 t：bag ，s[3] = g 和 t[2] = g是相同的，但是字符串s也可以不用s[3]来匹配，即用s[0]s[1]s[2]组成的bag。当然也可以用s[3]来匹配，即：s[0]s[1]s[3]组成的bag。

None b a g
None 1 0 0 0
b 0 1 0 0
a 0 1 1 0
g 0 1 1 1
g 0 1 1 2

  • 如果s[i - 1] == t[j - 1]，则dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]；

    • 解释：如果两个字符相等（当前为s[i - 1]和t[j - 1]子串），则s和t各退一步，对比前s[i - 2]和前t[j - 2]子串，所以dp[i - 1][j - 1] 需要被加上；
    • 此外，s需要额外退一步，即只对比前s[i - 2]和前t[j - 1]子串，比如当遍历到s[3]=g(第二个),t[2]=g，此时s[2]=g也是满足情况的（对应结果放在dp[2][2]），这个情况的结果也要被考虑进去，这一步才是能计算出多种方案的关键步骤

  • 如果s[i - 1] != t[j - 1]，则dp[i][j] = dp[i - 1][j]

    • 解释：相当于在不相等时，s了退一步，即只对比前s[i - 2]和前t[j - 1]子串， 前s[i - 2]个字符（对应dp[i - 1][j]） 的结果就是dp[i][j]的结果，比如s[1] = a，t[0] = b，他俩不相等，此时就去对比s[0] = b和t[0] = b，所以dp[1][0] = dp[0][0]

img

img

  1. 初始化

dp = [[0] * (len(s) + 1) for _ in range(len(s) + 1)]

第一列都初始化为1，第一行全为0

  1. 遍历顺序

纵向遍历t，横向遍历s

动态规划代码

  • 时间复杂度O(N*M)
  • 空间复杂度O(N*M)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def numDistinct(self, s: str, t: str) -> int:

        Ls = len(s)
        Lt = len(t)

        dp = [[0] * (Lt + 1) for _ in range(Ls + 1)]
        for i in range(Ls):
            dp[i][0] = 1

        for i in range(1, Ls + 1):
            for j in range(1, Lt + 1):
                if s[i - 1] == t[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
                else:
                    dp[i][j] = dp[i - 1][j]
        

        return dp[-1][-1]

583. 两个字符串的删除操作

https://leetcode.cn/problems/delete-operation-for-two-strings/

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。

每步 可以删除任意一个字符串中的一个字符。

示例 1：

1
2
3
输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"

示例 2:

1
2
输入：word1 = "leetcode", word2 = "etco"
输出：4

提示：

  • 1 <= word1.length, word2.length <= 500
  • word1 和 word2 只包含小写英文字母

动态规划思路一

题目可以修改成，找到最大公共子串长度x（这里的子串不用连续），结果是len(w1) - x + len(w2) - x

本题和动态规划：1143.最长公共子序列基本相同

  1. dp下标与含义

dp[i][j] 为w1[i - 1], w2[j - 1]的最大公共子串长度

  1. 递推公式

如果w1[i - 1]和w2[j - 1]相等，则dp[i][j] = dp[i - 1][j - 1] + 1，表示w1和w2各退一步，上一个字符的结果加一即可

如果w1[i - 1]和w2[j - 1]不相等，dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])，表示需要分成两种情况：

  • 让w1退一步，使用w1[i - 2]和w2[j - 1]的结果
  • 让w2退一步，使用w1[i - 1]和w2[j - 2]的结果
  • 当然，为了求最大公共子串长度，所以取两者最大值
  1. 初始化

dp = [[0] * (len(word2) + 1) for _ in range(len(word1) + 1)]

第一行、第一列全为0

  1. 遍历顺序

纵向对word1, 横向对word2

动态规划代码一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:

        Lw1 = len(word1)
        Lw2 = len(word2)
        dp = [[0] * (Lw2 + 1) for _ in range(Lw1 + 1)]

        for i in range(1, Lw1 + 1):
            for j in range(1, Lw2 + 1):
                if word1[i - 1] ==word2[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 Lw1 + Lw2 - 2 * dp[-1][-1]

动态规划思路二

本题和动态规划：115.不同的子序列相比，其实就是两个字符串都可以删除了，情况虽说复杂一些，但整体思路是不变的。

这次是两个字符串可以相互删了，这种题目也知道用动态规划的思路来解，动规五部曲，分析如下：

  1. 确定dp数组（dp table）以及下标的含义

dp[i][j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。

  1. 递推公式

当word1[i - 1] 与 word2[j - 1]相同的时候，dp[i][j] = dp[i - 1][j - 1];

当word1[i - 1] 与 word2[j - 1]不相同的时候，有三种情况：

情况一：删word1[i - 1]，最少操作次数为dp[i - 1][j] + 1

情况二：删word2[j - 1]，最少操作次数为dp[i][j - 1] + 1

情况三：同时删word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1][j - 1] + 2

那最后当然是取最小值，所以当word1[i - 1] 与 word2[j - 1]不相同的时候，递推公式：dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});

因为 dp[i][j - 1] + 1 = dp[i - 1][j - 1] + 2，

所以递推公式可简化为：dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;

  1. dp数组如何初始化

从递推公式中，可以看出来，dp[i][0] 和 dp[0][j]是一定要初始化的。

dp[i][0]：word2为空字符串，以i-1为结尾的字符串word1要删除多少个元素，才能和word2相同呢，很明显dp[i][0] = i。

dp[0][j]的话同理

  1. 确定遍历顺序

从递推公式 dp[i][j] = min(dp[i - 1][j - 1] + 2, min(dp[i - 1][j], dp[i][j - 1]) + 1); 和dp[i][j] = dp[i - 1][j - 1]可以看出dp[i][j]都是根据左上方、正上方、正左方推出来的。

所以遍历的时候一定是从上到下，从左到右，这样保证dp[i][j]可以根据之前计算出来的数值进行计算。

  1. 举例推导dp数组

以word1:“sea”，word2:"eat"为例，推导dp数组状态图如下：

583.两个字符串的删除操作1

72. 编辑距离

https://leetcode.cn/problems/edit-distance/

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

示例 1：

1
2
3
4
5
6
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：

1
2
3
4
5
6
7
8
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

提示：

  • 0 <= word1.length, word2.length <= 500
  • word1 和 word2 由小写英文字母组成

动态规划思路

  1. dp下标与含义：

dp[i][j] 表示把w1[i - 1]转成w2[j - 1]的最小操作数

  1. 递推公式

如果相等dp[i][j]=dp[i - 1][j - 1]

如果不相等，则需要有：1.删除 2.增加 3.替换操作

其中，删除操作有两种可能

1.1 删除word1里的一个字，即保留word1[i - 2]和word2[j - 1]，dp[i][j] = dp[i - 1][j] + 1

1.2 删除word2里的一个字，即保留word1[i - 1]和word2[j - 2]，dp[i][j] = dp[i][j - 1] + 1

而增加，对word1增加，可以看成对word2删除，所以公式和上面一样

而替换操作，由于不增加不减少，dp[i][j] = dp[i - 1][j - 1] + 1，只要在word1[i - 2]和word2[j - 2]基础上添加一次操作即可

所以

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])

PS： 这种二维dp[i][j]，一共只有三个方向能转移到dp[i][j]，所以在什么条件下，怎么进行转移才是重点

  1. 初始化

dp = [[0] * (len(word2) + 1) for _ in range(len(word1) + 1)]

那么dp[i][0] 和 dp[0][j] 表示什么呢？

dp[i][0] ：以下标i-1为结尾的字符串word1，和空字符串word2，最近编辑距离为dp[i][0]。

那么dp[i][0]就应该是i，对word1里的元素全部做删除操作，即：dp[i][0] = i;

同理dp[0][j] = j;

  1. 遍历顺序

注意word1是被操作对象，所以纵向遍历word1，横向遍历word2

从左到右、从上到下遍历

动态规划代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        
        Lw1 = len(word1)
        Lw2 = len(word2)
        dp = [[0] * (Lw2 + 1) for _ in range(Lw1 + 1)]

        # 初始化
        for i in range(Lw1 + 1):
            dp[i][0] = i
        for j in range(Lw2 + 1):
            dp[0][j] = j
        
        for i in range(1, Lw1 + 1):
            for j in range(1, Lw2 + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
        
        return dp[-1][-1]