LeetCode 287. 寻找重复数
给定一个包含 n + 1 个整数的数组 nums，其中每个整数都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 中只有一个重复的整数，返回这个重复的数。
要求设计的解决方案不修改数组 nums，且只使用常量级 O(1) 的额外空间。
法一：链表快慢指针
将数组视为链表，每个元素的值作为下一个节点的索引。由于存在重复元素，必然存在环。使用快慢指针检测环，并找到环的入口，即为重复的数。
class Solution: def findDuplicate(self, nums: List[int]) -> int: # 快慢指针初始化 slow = nums[0] fast = nums[0]
# 第一次循环，找到相遇点 while True: slow = nums[slow] # 慢指针走一步 fast = nums[nums[fast]] # 快指针走两步 if slow == fast: break
# 第二次循环，找到环的入口 slow = nums[0] # 将慢指针重新指向起点 while slow != fast: slow = nums[slow] # 慢指针走一步 fast = nums[fast] # 快指针走一步
return slow # 返回重复的数疑问：为什么要将慢指针重新指向起点？
将慢指针重新指向起点的原因是为了找到环的入口。第一次循环中，快慢指针相遇时，慢指针已经走了 k 步，而快指针走了 2k 步。设环的长度为 C，从起点到环入口的距离为 L，从环入口到相遇点的距离为 D。根据快慢指针的性质，我们可以得出以下关系：
-
慢指针走的总步数 =
L + D -
快指针走的总步数 =
L + D + nC（n是快指针绕环的圈数）因为快指针走了两倍于慢指针的步数，所以我们有：
2(L + D) = L + D + nC=> L + D = nC=> L = nC - D这意味着从起点到环入口的距离 L 等于从相遇点沿着环走到环入口所需的距离。因此，当我们将慢指针重新指向起点，并让快慢指针同时以相同速度前进时，它们将在环入口相遇，从而找到重复的数。
数据范围变化时的注意事项
如果数字的范围从 [1, n] 变成了 [0, n-1]，那么不能从下标 0 开始遍历了，而必须从下标 n 开始。
核心原因：必须保证有一个“绝对的头节点”，弗洛伊德判圈算法（快慢指针）要找到环的入口，前提是链表必须有一个明确的起点（头节点），并且从这个起点出发，能顺利走到环里。
-
在原题
[1, n]中： 数组下标是0到n，但数组里的值只有1到n。 这意味着：没有任何一个元素的值等于 0。 所以，下标0是一个**“只出不进”**的节点。从nums[0]出发，你一定会先走一段“非环”的路径，然后进入环。0就是完美的天然头节点。 -
如果改成
[0, n-1]： 数组下标是0到n-1，数组里的值也是0到n-1。 这时候，没有任何一个下标是安全的。因为数组里包含了0，必然有某个位置nums[i] = 0。 如果你从下标0开始，第一步走到nums[0]，第二步可能又走回0，或者走到某个环里。你无法确定0是在环外还是环内，算法的数学推导（）就会失效。
法二：二分查找法
以示例 1 为例，我们列出每个数字的 cnt 值：
| nums | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| cnt | 1 | 3 | 4 | 5 |
知道 cnt[] 数组随数字 i 逐渐增大具有单调性，那么我们就可以直接利用二分查找来找到重复的数。
具体思路：
- 初始化左边界
left为 1，右边界right为len(nums) - 1。 - 在
[left, right]范围内进行二分查找，计算中间值mid。 - 统计数组中小于等于
mid的元素个数count。 - 根据
count更新搜索范围：- 如果
count > mid，说明重复数字在[left, mid]范围内，将右边界right更新为mid。 - 否则，说明重复数字在
[mid + 1, right]范围内，将左边界left更新为mid + 1。
- 如果
class Solution: def findDuplicate(self, nums: List[int]) -> int: left, right = 1, len(nums) - 1 # 为什么右边界是 len(nums) - 1？因为数组中数字的范围是 [1, n]，而数组长度是 n + 1，所以右边界应该是 n，即 len(nums) - 1。 while left < right: mid = (left + right) // 2 # 计算中间值，// 2 为整除，确保 mid 为整数 # 使用生成器表达式统计小于等于 mid 的元素个数，避免额外空间开销 count = sum(num <= mid for num in nums) if count > mid: right = mid else: left = mid + 1 return left疑惑点 1：为什么 count 要这么计算？为什么要统计小于等于 mid 的元素个数？
因为我们需要知道在 [1, mid] 范围内有多少个元素，这样可以判断是否有重复的数字。如果 count > mid，说明在 [1, mid] 范围内有超过 mid 个元素，而这个范围只有 mid 个不同的数字，所以必然有至少一个数字重复。
疑惑点 2：为什么 count > mid 时，重复数字一定在 [left, mid] 范围内？
因为如果 count > mid，说明在 [1, mid] 范围内有超过 mid 个元素，而这个范围只有 mid 个不同的数字，所以必然有至少一个数字重复。因此，重复的数字一定在 [left, mid] 范围内。
LeetCode 31：下一个排列
整数数组的一个排列就是将其所有成员以序列或线性顺序排列。
例如，arr = [1, 2, 3]，以下这些都可以视作 arr 的排列：[1, 2, 3]、[1, 3, 2]、[3, 1, 2]、[2, 3, 1]。
整数数组的下一个排列是指其字典序中的下一个更大排列。更正式地，如果数组的所有排列根据字典顺序从小到大排列在一个容器中，那么下一个排列就是在这个有序容器中排在当前排列后面的那个排列。如果不存在下一个更大的排列，那么数组必须重排为字典序最小的排列，即按升序排列。
例如，arr = [1, 2, 3] 的下一个排列是 [1, 3, 2]。
类似地，arr = [2, 3, 1] 的下一个排列是 [3, 1, 2]。
而 arr = [3, 2, 1] 的下一个排列是 [1, 2, 3]，因为 [3, 2, 1] 不存在字典序更大的排列。
给你一个整数数组 nums，找出 nums 的下一个排列。
必须原地修改，只允许使用常数级额外空间。
思路
- 从后往前找到第一个满足
nums[i] < nums[i + 1]的位置i。 - 在
[i + 1, n - 1]中找到最右侧的大于nums[i]的数并交换。 - 将
[i + 1, n - 1]逆序，使后缀尽可能小。 - 如果整个数组是降序排列，则直接将整个数组逆序。
class Solution: def nextPermutation(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ n = len(nums) # 从后往前找到第一个升序对 i = n - 2 while i >= 0 and nums[i] >= nums[i + 1]: i -= 1 if i == -1: # 整个数组是降序排列 nums.reverse() else: # 找到最右侧的大于 nums[i] 的数 j = n - 1 while nums[j] <= nums[i]: j -= 1 # 交换 nums[i] 和 nums[j] nums[i], nums[j] = nums[j], nums[i] # 将 [i + 1, n - 1] 逆序，让后缀尽可能小 nums[i + 1:] = reversed(nums[i + 1:])LeetCode 75. 颜色分类
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
思路
常规思路：统计每种颜色的数量，然后根据计数重新填充数组。
class Solution: def sortColors(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ count = [0, 0, 0] # 计数器，分别统计 0、1、2 的数量 for num in nums: count[num] += 1 i = 0 for j in range(3): for _ in range(count[j]): nums[i] = j i += 1方法一：单指针
使用单指针，先通过一次遍历交换整理好红色区域，再通过第二次遍历交换整理好白色区域，蓝色区域自然就排好了。
class Solution: def sortColors(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ n = len(nums) p0 = 0 # 红色区域的末尾指针 for i in range(n): if nums[i] == 0: nums[i], nums[p0] = nums[p0], nums[i] p0 += 1 p1 = p0 # 白色区域的末尾指针 for i in range(p0, n): if nums[i] == 1: nums[i], nums[p1] = nums[p1], nums[i] p1 += 1方法二：双指针
使用双指针方法，将数组分为三部分，分别表示红色、白色和蓝色。
具体思路：
p0指向下一个应放置0的位置，p1指向下一个应放置1的位置。- 遍历数组：遇到
1时，将其交换到p1，然后p1右移。 - 遇到
0时，先将其交换到p0。如果p0 < p1，说明被换到当前位置的元素属于白色区域，还需要将它交换到p1，随后p0和p1都右移。 - 遇到
2时不需要额外处理，它会留在数组后部；遍历结束后，数组即按0、1、2的顺序排列。
class Solution: def sortColors(self, nums: List[int]) -> None: n = len(nums) p0 = p1 = 0 for i in range(n): if nums[i] == 1: nums[i], nums[p1] = nums[p1], nums[i] p1 += 1 elif nums[i] == 0: nums[i], nums[p0] = nums[p0], nums[i] if p0 < p1: #为什么要判断 p0 < p1？因为如果 p0 < p1，说明原本在p0位置的元素属于白色区域，还需要将它交换到 p1。 nums[i], nums[p1] = nums[p1], nums[i] p0 += 1 p1 += 1方法三：三指针
使用三指针方法，将数组分为三部分，分别表示红色、白色和蓝色。
具体思路：
- 初始化三个指针：
red指向红色区域的末尾。 white指向当前处理的元素。blue指向蓝色区域的开头。- 当
white指针小于等于blue指针时，进行如下操作：- 如果
nums[white]为 0，则将其与nums[red]交换，并将red和white指针都向右移动。 - 如果
nums[white]为 1，则只将white指针向右移动。 - 如果
nums[white]为 2，则将其与nums[blue]交换，并将blue指针向左移动。
- 如果
class Solution: def sortColors(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ # 三指针方法 red, white, blue = 0, 0, len(nums) - 1 while white <= blue: if nums[white] == 0: nums[red], nums[white] = nums[white], nums[red] red += 1 white += 1 elif nums[white] == 1: white += 1 else: nums[white], nums[blue] = nums[blue], nums[white] blue -= 1疑问：交换后的元素如何保证 white 指针不会跳过未处理的元素？
实际上，除了 nums[white] == 1 时 white 指针会向右移动，其他情况下白色区域并没有扩大，white 指针仍然指向未处理的元素，因此不会跳过未处理的元素。例如，当 nums[white] == 0 时，看似 white 指针向右移动了，但实际上 white 指针指向的元素已经被交换到了 red 指针的位置.
LeetCode 169. 多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
法一：哈希表 思路：遍历数组，使用哈希表记录每个元素的出现次数，然后找出出现次数大于 ⌊ n/2 ⌋ 的元素。
class Solution: def majorityElement(self, nums: List[int]) -> int: count = {} for num in nums: count[num] = count.get(num, 0) + 1 #count.get(num, 0) 的作用是获取 num 在字典 count 中的当前计数，如果 num 不存在于 count 中，则返回默认值 0。然后将计数加 1，表示 num 出现了一次。 if count[num] > len(nums) // 2: return num法二：摩尔投票算法 思路：利用多数元素的特性，通过投票的方式找出多数元素。
- 初始化候选元素
candidate和计数器count。 - 遍历数组，如果当前元素与候选元素相同，则
count加 1；否则count减 1。 - 如果
count为 0，则更新候选元素为当前元素，并将count设为 1。 - 遍历结束后，候选元素即为多数元素。
class Solution: def majorityElement(self, nums: List[int]) -> int: candidate = None #None 是 Python 中的一个特殊对象，表示“没有值”或“空值”。类似于其他编程语言中的 null 或 nil。它通常用于表示变量尚未被赋值，或者函数没有返回值的情况。在这里，candidate 被初始化为 None，表示当前还没有确定的候选多数元素。 count = 0 for num in nums: if count == 0: candidate = num if num == candidate: count += 1 else: count -= 1 return candidateLeetCode 136. 只出现一次的数字
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
由于此处要求使用线性时间复杂度和常量空间复杂度，因此可以使用位运算中的异或操作来解决这个问题。
思路：
- 初始化一个变量
result为 0。 - 遍历数组中的每个元素，将其与
result进行异或操作。 - 由于异或操作的性质：
- 相同的数异或结果为 0（即
a ^ a = 0）。 - 任何数与 0 异或结果为其本身（即
a ^ 0 = a）。 - 异或操作满足交换律和结合律。
- 因此，数组中成对出现的数字会相互抵消，最终
result中只会剩下那个只出现一次的数字。
- 相同的数异或结果为 0（即
- 返回
result。
class Solution: def singleNumber(self, nums: List[int]) -> int: result = 0 for num in nums: result ^= num # 使用异或操作，将当前数字与结果进行异或 return resultLeetCode 62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start（1，1）” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish（m，n）” ）。
问总共有多少条不同的路径？
动态规划法： 1.边界条件：
- 当网格只有1行时，它只能向右移动，因此第一行的所有格子只有一条路径，即
dp[0][j] = 1。 - 当网格只有1列时，它只能向下移动，因此第一列的所有格子也只有一条路径，即
dp[i][0] = 1。 2.状态转移方程： - 对于其他格子
(i, j)，机器人可以从上方的格子(i-1, j)或左方的格子(i, j-1)移动过来。因此，路径总数为：dp[i][j] = dp[i-1][j] + dp[i][j-1]
3.初始条件：
dp[0][0] = 1，表示起点只有一条路径。dp[0][j] = 1，表示第一行的所有格子只有一条路径。dp[i][0] = 1，表示第一列的所有格子只有一条路径。
class Solution: def uniquePaths(self, m: int, n: int) -> int: # 创建一个 m x n 的二维数组 dp，用于存储每个格子的路径数 dp = [[0] * n for _ in range(m)] #此处使用列表推导式创建了一个 m 行 n 列的二维数组 dp，并初始化为 0。`[[0] * n for _ in range(m)]` 的含义是：对于每一行（总共有 m 行），创建一个包含 n 个 0 的列表，从而形成一个 m x n 的矩阵。
# 初始化第一行和第一列的路径数为 1 for i in range(m): dp[i][0] = 1 for j in range(n): dp[0][j] = 1
# 使用动态规划计算每个格子的路径数 for i in range(1, m): for j in range(1, n): dp[i][j] = dp[i-1][j] + dp[i][j-1]
# 返回右下角格子的路径数，即总路径数 return dp[m-1][n-1]LeetCode 64. 最小路径和
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
解法：动态规划 1.边界条件：
- 当网格只有1行时，它只能向右移动，因此第一行的所有格子只有一条路径，即该行的路径和为该行所有元素的累加和。
- 当网格只有1列时，它只能向下移动，因此第一列的所有格子也只有一条路径，即该列的路径和为该列所有元素的累加和。
- 当网格只有一个格子时，该格子的路径和为其本身的值。 2.状态转移方程：
- 对于其他格子
(i, j)，机器人可以从上方的格子(i-1, j)或左方的格子(i, j-1)移动过来。因此，路径总和为：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
3.初始条件：
dp[0][0] = grid[0][0]，表示起点的路径和为其本身的值。dp[0][j] = dp[0][j-1] + grid[0][j]，表示第一行的路径和为前一个格子的路径和加上当前格子的值。dp[i][0] = dp[i-1][0] + grid[i][0]，表示第一列的路径和为前一个格子的路径和加上当前格子的值。
class Solution: def minPathSum(self, grid: list[list[int]]) -> int:
m, n = len(grid), len(grid[0]) dp = [[0] * n for _ in range(m)]
dp[0][0] = grid[0][0]
# 初始化第一行 for j in range(1, n): dp[0][j] = dp[0][j-1] + grid[0][j]
# 初始化第一列 for i in range(1, m): dp[i][0] = dp[i-1][0] + grid[i][0]
# 动态规划填表 for i in range(1, m): for j in range(1, n): dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
return dp[m-1][n-1]Leetcode 5. 最长回文子串
给你一个字符串 s，找到 s 中最长的 回文 子串。
解法：动态规划 1.边界条件：
- 当字符串长度为 1 时，最长回文子串就是字符串本身,dp[i][i]=1。
- 当字符串长度为 2 时，如果两个字符相同，则最长回文子串为这两个字符，否则为任意一个字符。
2.状态转移方程：
dp[i][j] 表示字符串 s 从索引 i 到 j 的子串是否为回文子串。
dp[i][j] = True 当且仅当 s[i] == s[j] dp[i][j] = True 当且仅当 s[i] == s[j] 且 dp[i+1][j-1] 为 True（即子串 s[i+1] 也是回文子串）。 3.初始条件： dp[i][i] = True，表示单个字符是回文子串。dp[i][i+1] = (s[i] == s[i+1])，表示两个相邻字符是否构成回文子串。
class Solution: def longestPalindrome(self, s: str) -> str: n = len(s) if n < 2: return s
# 初始化动态规划表 dp = [[False] * n for _ in range(n)] start, max_len = 0, 1
# 所有长度为 1 的子串都是回文 for i in range(n): dp[i][i] = True
# 检查长度为 2 的子串 for i in range(n - 1): if s[i] == s[i + 1]: dp[i][i + 1] = True start = i max_len = 2
# 检查长度大于 2 的子串 for length in range(3, n + 1): # 子串长度从 3 到 n for i in range(n - length + 1): j = i + length - 1 if s[i] == s[j] and dp[i + 1][j - 1]: dp[i][j] = True start = i max_len = length
return s[start:start + max_len] #此处左闭右开，取到的子串是从索引 start 开始，长度为 max_len 的子串。优化一：统一处理长度不小于 2 的子串
可以让区间 DP 从长度 2 开始。原转移式在长度为 2 时会访问 dp[i + 1][i]（当j-1=i时），即一个未定义的空区间，因此原实现才需要单独处理长度为 2 的子串。
加入 length == 2 的判断后，长度为 2 和长度大于 2 的子串便可以使用同一个循环：
class Solution: def longestPalindrome(self, s: str) -> str: n = len(s) if n < 2: return s
dp = [[False] * n for _ in range(n)] start, max_len = 0, 1
for i in range(n): dp[i][i] = True
for length in range(2, n + 1): for i in range(n - length + 1): j = i + length - 1 if s[i] == s[j] and (length == 2 or dp[i + 1][j - 1]): #当 length == 2 时，直接判断 s[i] == s[j] 即可，无需访问 dp[i + 1][j - 1]。 dp[i][j] = True if length > max_len: start, max_len = i, length
return s[start:start + max_len]也可以将条件写成更通用的形式：
dp[i][j] = s[i] == s[j] and (j - i < 2 or dp[i + 1][j - 1])其中 j - i < 2 同时覆盖长度为 1 和长度为 2 的情况。
优化二：将二维 DP 压缩为一维 DP
dp[i][j] 只会使用主对角线及其右上方的区域。仅存储上三角虽然能减少约一半的实际空间，但空间复杂度仍是 O(n²)。
由于当前状态只依赖 dp[i + 1][j - 1]，可以用一维数组滚动保存状态(从右上三角的右下角开始，逐行向上更新；每一行从右向左更新)，将空间复杂度降为 O(n)：
class Solution: def longestPalindrome(self, s: str) -> str: n = len(s) if n < 2: return s
dp = [False] * n start, max_len = 0, 1
# 当前外层循环计算左端点为 i 的所有区间。 for i in range(n - 1, -1, -1): #从（n-1,-1,-1）表示从 n-1 到 0（包含 0），步长为 -1，即逆序遍历。 # 必须从右向左更新，确保 dp[j - 1] 仍表示 # 上一轮的二维状态 dp[i + 1][j - 1]。 for j in range(n - 1, i - 1, -1): dp[j] = s[i] == s[j] and (j - i < 2 or dp[j - 1])
current_len = j - i + 1 if dp[j] and current_len > max_len: start, max_len = i, current_len
return s[start:start + max_len]优化后的时间复杂度仍为 O(n²)，额外空间复杂度由 O(n²) 降为 O(n)。这里 j 的遍历方向非常重要：如果从左向右更新，dp[j - 1] 会被当前轮提前覆盖，不再表示所需的 dp[i + 1][j - 1]。
LeetCode 1143. 最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
方法一：动态规划
1.边界条件：
- 当其中一个字符串为空时，最长公共子序列的长度为 0。
2.状态转移方程：dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列的长度。
- 如果 text1[i - 1] == text2[j - 1]，则dp[i][j] = dp[i - 1][j - 1] + 1。
- 如果 text1[i - 1] != text2[j - 1]，则dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])。
3.初始条件：
- dp[0][j] = 0，表示 text1 为空时，最长公共子序列的长度为 0。
- dp[i][0] = 0，表示 text2 为空时，最长公共子序列的长度为 0。
class Solution: def longestCommonSubsequence(self, text1: str, text2: str) -> int: m, n = len(text1), len(text2) dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1): for j in range(1, n + 1): if text1[i - 1] == text2[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]LeetCode 72. 编辑距离
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作： 插入一个字符 删除一个字符 替换一个字符
方法一：动态规划
1.边界条件：
- 当其中一个单词为空时，编辑距离为另一个单词的长度。
2.状态转移方程：dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作数（dp[i][j]代表此时word1的前i个字符已经与word2的前j个字符匹配）。
- 如果 word1[i - 1] == word2[j - 1]，则 dp[i][j] = dp[i - 1][j - 1]。
- 如果 word1[i - 1] != word2[j - 1]，则 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1。
3.初始条件：
- dp[0][j] = j，表示将空字符串转换为 word2 的前 j 个字符需要 j 次插入操作。
- dp[i][0] = i，表示将 word1 的前 i 个字符转换为空字符串需要 i 次删除操作。
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 + 1): dp[i][0] = i # word2 为空时，编辑距离为 word1 的长度 for j in range(n + 1): dp[0][j] = j # word1 为空时，编辑距离为 word2 的长度
for i in range(1, m + 1): for j in range(1, n + 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[m][n]注意：把 dp[i][j] 理解为：把 word1 的前 i 个字符，变成 word2 的前 j 个字符，最少需要几步。当两个前缀的最后一个字符不同时，可以考虑最后一步做了什么：
- dp[i-1][j] + 1：先把 word1 的前 i-1 个字符变成目标，再删除 word1 的第 i 个字符。
- dp[i][j-1] + 1：先变成 word2 的前 j-1 个字符，再向结果中插入 word2 的第 j 个字符。
- dp[i-1][j-1] + 1：先处理两边各少一个字符的前缀，再把末尾字符替换掉。
如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时