class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m):
for j in range(n):
if word1[i] == word2[j]:
dp[i+1][j+1] = dp[i][j] + 1
else:
dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
return m + n - dp[m][n] * 2
相关文章
- 12-15代码随想录第45天-583. 两个字符串的删除操作
- 12-15代码随想录算法训练营第46期Day37,38,39,41-而m 和 n相当于是一个背包,两个维度的背包。 理解成多重背包的同学主要是把m和n混淆为物品了,感觉这是不同数量的物品,所以以为是多重背包。 但本题其实是01背包问题! 只不过这个背包有两个维度,一个是m 一个是n,而不同长度的字符串就是不同大小的待装物品。 开始动规五部曲: 确定dp数组(dp table)以及下标的含义 dp[i][j]:最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。 确定递推公式 dp[i][j] 可以由前一个strs里的字符串推导出来,strs里的字符串有zeroNum个0,oneNum个1。 dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。 然后我们在遍历的过程中,取dp[i][j]的最大值。 所以递推公式:dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1); 此时大家可以回想一下01背包的递推公式:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); 对比一下就会发现,字符串的zeroNum和oneNum相当于物品的重量(weight[i]),字符串本身的个数相当于物品的价值(value[i])。 这就是一个典型的01背包! 只不过物品的重量有了两个维度而已。 dp数组如何初始化 01背包的dp数组初始化为0就可以。 因为物品价值不会是负数,初始为0,保证递推的时候dp[i][j]不会被初始值覆盖。 确定遍历顺序 01背包一定是外层for循环遍历物品,内层for循环遍历背包容量 那么本题也是,物品就是strs里的字符串,背包容量就是题目描述中的m和n。(相当于之前的一维dp,采用了滚动数组) 倒序遍历是为了保证物品i只被放入一次!。但如果一旦正序遍历了,那么物品0就会被重复加入多次! 那么问题又来了,为什么二维dp数组遍历的时候不用倒序呢?
- 12-15代码随想录第56天 | 583. 两个字符串的删除操作 、 72. 编辑距离
- 12-15583.两个字符串的删除操作
- 12-15583.两个字符串的删除操作
- 12-15【动态规划】583. 两个字符串的删除操作
- 12-15力扣:583. 两个字符串的删除操作