题目链接

关键词

解析

• 状态定义： 定义 dp[i][j] 表示把 word1 前 i 个字符变成和 word2 前 j 个字符一样的最少操作数

• 状态方程：
• word1[i] == word2[j]：dp[i][j] = dp[i - 1][j - 1]
• word1[i] != word2[j]：
• 删除操作： word1[i - 1] == word2[j], dp[i][j] = dp[i - 1][j] + 1 word1[i] == word2[j - 1], dp[i][j] = dp[i][j - 1] + 1
• 插入操作： word1[i - 1] == word2[j], dp[i][j] = dp[i - 1][j] + 1 word1[i] == word2[j - 1], dp[i][j] = dp[i][j - 1] + 1
• 替换操作： dp[i][j] = dp[i - 1][j - 1] + 1

代码

相似题目