动态规划问题： LeetCode - 72. 编辑距离

72. 编辑距离

题目描述

给出两个字符串 word1 与 word2，要求计算将 word1 转化为 word2 所需执行的最少操作次数。

对于一个字符串，允许进行以下三种操作：

添加一个字符
移除一个字符
更改一个字符

示例 1：

输入：word1 = “horse”，word2 = “ros”
输出：3
说明：
horse → rorse（将 ‘h’ 替换为 ‘r’）
rorse → rose（删除 ‘r’）
rose → ros（删除 ‘e’）

示例 2：

输入：word1 = “intention”，word2 = “execution”
输出：5
说明：
intention → inention（删除 ‘t’）
inention → enention（将 ‘i’ 替换为 ‘e’）
enention → exention（将 ‘n’ 替换为 ‘x’）
exention → exection（将 ‘n’ 替换为 ‘c’）
exection → execution（插入 ‘u’）

解题思路

思路

1. 可分为两种情形，① 字符一致，② 字符不一致

• 当字