多维动态规划
不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
- 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右
- 向下 -> 向右 -> 向下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
from typing import List
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
"""
使用动态规划求解不同路径数量
思路：
- dp[i][j] 表示从起点 (0,0) 到位置 (i,j) 的路径数
- 机器人只能向右或向下移动
- dp[i][j] = dp[i-1][j] + dp[i][j-1]（从上方来 + 从左方来）
- 第一行和第一列只有一种走法（全部向右或全部向下）
- 时间 O(m*n)，空间 O(m*n)，可优化到 O(n)
例如 3x3 网格：
dp = [
[1, 1, 1],
[1, 2, 3],
[1, 3, 6]
]
"""
# 初始化 dp 表
dp = [[1] * n for _ in range(m)]
# 填充 dp 表
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]
def uniquePaths_optimized(self, m: int, n: int) -> int:
"""
空间优化版本
思路：
- 只用一维数组 dp[j] 表示当前行的路径数
- dp[j] = dp[j] + dp[j-1]
- dp[j] 是上一行的值（从上方来）
- dp[j-1] 是当前行已更新的值（从左方来）
- 时间 O(m*n)，空间 O(n)
"""
dp = [1] * n # 初始化第一行
for i in range(1, m):
for j in range(1, n):
dp[j] += dp[j - 1]
return dp[n - 1]
# 测试用例
assert Solution().uniquePaths(3, 7) == 28
assert Solution().uniquePaths(3, 2) == 3
assert Solution().uniquePaths(7, 3) == 28
assert Solution().uniquePaths(3, 3) == 6
assert Solution().uniquePaths(1, 1) == 1
assert Solution().uniquePaths(1, 5) == 1
assert Solution().uniquePaths(5, 1) == 1
# 手动推导 m=3, n=7：
# dp 表初始状态（第一行和第一列都是1）：
# j: 0 1 2 3 4 5 6
# i=0: 1 1 1 1 1 1 1
# i=1: 1 ? ? ? ? ? ?
# i=2: 1 ? ? ? ? ? ?
#
# 逐格计算：
# i=1, j=1: dp[1][1] = 1+1 = 2
# i=1, j=2: dp[1][2] = 1+2 = 3
# i=1, j=3: dp[1][3] = 1+3 = 4
# i=1, j=4: dp[1][4] = 1+4 = 5
# i=1, j=5: dp[1][5] = 1+5 = 6
# i=1, j=6: dp[1][6] = 1+6 = 7
#
# i=2, j=1: dp[2][1] = 1+2 = 3
# i=2, j=2: dp[2][2] = 2+3 = 5
# i=2, j=3: dp[2][3] = 3+5 = 8
# i=2, j=4: dp[2][4] = 4+8 = 12
# i=2, j=5: dp[2][5] = 5+12 = 17
# i=2, j=6: dp[2][6] = 6+17 = 23... 不对
#
# 重新计算：
# i=1, j=1: dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2
# i=1, j=2: dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3
# i=1, j=3: dp[1][3] = dp[0][3] + dp[1][2] = 1 + 3 = 4
# i=1, j=4: dp[1][4] = dp[0][4] + dp[1][3] = 1 + 4 = 5
# i=1, j=5: dp[1][5] = dp[0][5] + dp[1][4] = 1 + 5 = 6
# i=1, j=6: dp[1][6] = dp[0][6] + dp[1][5] = 1 + 6 = 7
#
# i=2, j=1: dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3
# i=2, j=2: dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6
# i=2, j=3: dp[2][3] = dp[1][3] + dp[2][2] = 4 + 6 = 10
# i=2, j=4: dp[2][4] = dp[1][4] + dp[2][3] = 5 + 10 = 15
# i=2, j=5: dp[2][5] = dp[1][5] + dp[2][4] = 6 + 15 = 21
# i=2, j=6: dp[2][6] = dp[1][6] + dp[2][5] = 7 + 21 = 28
#
# 最终 dp 表：
# j: 0 1 2 3 4 5 6
# i=0: 1 1 1 1 1 1 1
# i=1: 1 2 3 4 5 6 7
# i=2: 1 3 6 10 15 21 28
#
# 结果：dp[2][6] = 28
|
最小路径和
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
|
from typing import List
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
"""
使用动态规划求最小路径和
思路：
- dp[i][j] 表示从左上角到位置 (i,j) 的最小路径和
- dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
（从上方来 或 从左方来，取较小者）
- 第一行只能从左边来
- 第一列只能从上方来
- 时间 O(m*n)，空间可优化到 O(n)
例如 grid = [[1,3,1],[1,5,1],[4,2,1]]：
dp = [
[1, 4, 5],
[2, 7, 6],
[6, 8, 7]
]
"""
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
# 初始化 dp 表
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] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
return dp[m - 1][n - 1]
def minPathSum_optimized(self, grid: List[List[int]]) -> int:
"""
空间优化版本：只用一行 dp
思路：
- dp[j] 表示当前行第 j 列的最小路径和
- dp[j] = grid[i][j] + min(dp[j], dp[j-1])
- dp[j] 是上一行的值（从上方来）
- dp[j-1] 是当前行已更新的值（从左方来）
- 时间 O(m*n)，空间 O(n)
"""
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
dp = [float('inf')] * n
dp[0] = 0
for i in range(m):
for j in range(n):
if j == 0:
dp[j] = dp[j] + grid[i][j] # 从上方来
else:
dp[j] = grid[i][j] + min(dp[j], dp[j - 1]) # min(从上方，从左方)
return dp[n - 1]
# 测试用例
assert Solution().minPathSum([[1, 3, 1], [1, 5, 1], [4, 2, 1]]) == 7
assert Solution().minPathSum([[1, 2, 3], [4, 5, 6]]) == 12
assert Solution().minPathSum([[1]]) == 1
assert Solution().minPathSum([[1, 2]]) == 3
assert Solution().minPathSum([[1], [2]]) == 3
# 手动推导 grid = [[1,3,1],[1,5,1],[4,2,1]]：
# dp 表计算过程：
# 初始: dp[0][0] = 1
#
# 第一行（只能从左边来）：
# dp[0][1] = 1 + 3 = 4
# dp[0][2] = 4 + 1 = 5
#
# 第二行：
# dp[1][0] = 1 + 1 = 2（只能从上方来）
# dp[1][1] = 5 + min(4, 2) = 5 + 2 = 7
# dp[1][2] = 1 + min(5, 7) = 1 + 5 = 6
#
# 第三行：
# dp[2][0] = 2 + 4 = 6（只能从上方来）
# dp[2][1] = 2 + min(7, 6) = 2 + 6 = 8
# dp[2][2] = 1 + min(6, 8) = 1 + 6 = 7
#
# 最终 dp 表：
# [1, 4, 5]
# [2, 7, 6]
# [6, 8, 7]
#
# 路径：1 -> 3 -> 1 -> 1 -> 1 = 7
|
最长回文子串
给你一个字符串 s，找到 s 中最长的 回文 子串。
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。
s 仅由数字和英文字母组成
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
from typing import List
class Solution:
def longestPalindrome(self, s: str) -> str:
"""
使用中心扩展法找最长回文子串
思路：
- 回文串以某个位置为中心对称
- 中心有两种情况：
1. 单字符中心：如 "aba"，中心是 'b'
2. 双字符中心：如 "abba"，中心是 'bb'
- 从每个位置向两边扩展，比较两侧字符是否相等
- 记录最长的回文串
优化：
- 预处理：连续相同字符可以跳过，减少重复计算
- 时间 O(n^2)，空间 O(1)
例如 "babad"：
- 以 'b' 为中心扩展，发现 "bab" 是回文
- 以 'a' 为中心扩展，发现 "aba" 是回文
- 最长回文是 "bab" 或 "aba"
"""
if not s:
return ""
start, end = 0, 0 # 记录最长回文的起止位置
def expand_around_center(left: int, right: int) -> tuple:
"""以 left-1, right+1 为起点向两边扩展"""
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
# 返回本次扩展得到的回文范围（左闭右开）
return left + 1, right
for i in range(len(s)):
# 以单字符为中心扩展（如 "aba"）
left1, right1 = expand_around_center(i, i)
# 以双字符为中心扩展（如 "abba"）
left2, right2 = expand_around_center(i, i + 1)
# 选择更长的回文
if right1 - left1 > end - start:
start, end = left1, right1
if right2 - left2 > end - start:
start, end = left2, right2
return s[start:end]
def longestPalindrome_dp(self, s: str) -> str:
"""
动态规划解法
思路：
- dp[i][j] 表示 s[i:j+1] 是否为回文串
- dp[i][j] = (s[i] == s[j]) and (j - i < 2 or dp[i+1][j-1])
即：两端相等 且（长度<=2 或 中间也是回文）
- 从短到长填表
时间 O(n^2)，空间 O(n^2)
"""
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
# 枚举长度（从2开始）
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
if length == 2:
dp[i][j] = True
else:
dp[i][j] = dp[i + 1][j - 1]
if dp[i][j] and length > max_len:
start = i
max_len = length
return s[start:start + max_len]
# 测试用例
assert Solution().longestPalindrome("babad") in ["bab", "aba"]
assert Solution().longestPalindrome("cbbd") == "bb"
assert Solution().longestPalindrome("a") == "a"
assert Solution().longestPalindrome("ac") in ["a", "c"]
assert Solution().longestPalindrome("aacbcaa") == "aacbcaa"
assert Solution().longestPalindrome("aaaa") == "aaaa"
# 手动推导 "babad"：
# i=0, s[0]='b':
# 单中心扩展: left=0,right=0 -> 'b' 是回文 -> left=-1,right=1 越界
# 双中心扩展: left=0,right=1 -> 'b'!='a'，无法扩展
# 最长: "b" (长度1)
#
# i=1, s[1]='a':
# 单中心扩展: left=1,right=1 -> 'a' 是回文
# left=0,right=2 -> 'b'=='b'，继续 -> left=-1,right=3 越界
# 得到 "bab" (长度3)
# 双中心扩展: left=1,right=2 -> 'a'=='b'，无法扩展
# 最长: "bab" (长度3)
#
# i=2, s[2]='b':
# 单中心扩展: left=2,right=2 -> 'b' 是回文
# left=1,right=3 -> 'a'!='d'，停止
# 双中心扩展: left=2,right=3 -> 'b'!='d'，无法扩展
# 最长: "b" (长度1)
#
# i=3, s[3]='a':
# 单中心扩展: left=3,right=3 -> 'a' 是回文
# left=2,right=4 -> 'b'!='d'，停止
# 双中心扩展: left=3,right=4 -> 'a'!='d'，无法扩展
#
# i=4, s[4]='d':
# 单中心扩展: "d" (长度1)
#
# 最终最长回文: "bab" 或 "aba"
|
最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace” ，它的长度为 3 。
text1 和 text2 仅由小写英文字符组成
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
from typing import List
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
"""
使用动态规划求最长公共子序列长度
思路：
- dp[i][j] 表示 text1[0:i] 和 text2[0:j] 的最长公共子序列长度
- 如果 text1[i-1] == text2[j-1]：
dp[i][j] = dp[i-1][j-1] + 1
- 否则：
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
- 时间 O(m*n)，空间可优化到 O(min(m,n))
例如 text1="abcde", text2="ace"：
dp = [
[0, 0, 0, 0],
[0, 1, 1, 1],
[0, 1, 1, 1],
[0, 1, 2, 2],
[0, 1, 2, 2],
[0, 1, 2, 3]
]
最长公共子序列为 "ace"，长度为 3
"""
m, n = len(text1), len(text2)
# 初始化 dp 表（m+1 x n+1，多一行一列便于处理边界）
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]
def longestCommonSubsequence_optimized(self, text1: str, text2: str) -> int:
"""
空间优化版本：只用两行 dp
思路：
- 当前行只依赖上一行和当前行的左边
- 用两行数组交替使用
- 时间 O(m*n)，空间 O(n)
"""
m, n = len(text1), len(text2)
# 确保 text2 是较短的字符串，用较少的空间
if m < n:
text1, text2 = text2, text1
m, n = n, m
# 只用两行
prev = [0] * (n + 1)
curr = [0] * (n + 1)
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
curr[j] = prev[j - 1] + 1
else:
curr[j] = max(prev[j], curr[j - 1])
prev, curr = curr, prev
return prev[n]
# 测试用例
assert Solution().longestCommonSubsequence("abcde", "ace") == 3
assert Solution().longestCommonSubsequence("abc", "abc") == 3
assert Solution().longestCommonSubsequence("abc", "def") == 0
assert Solution().longestCommonSubsequence("", "") == 0
assert Solution().longestCommonSubsequence("", "abc") == 0
assert Solution().longestCommonSubsequence("abc", "") == 0
assert Solution().longestCommonSubsequence("abcba", "abcda") == 4 # "abca"
assert Solution().longestCommonSubsequence("bl", "yby") == 1 # "b" 或 "y"
# 手动推导 text1="abcde", text2="ace"：
# dp 表 (行: text1, 列: text2)
# "" a c e
# "" 0 0 0 0
# a 0 1 1 1
# b 0 1 1 1
# c 0 1 2 2
# d 0 1 2 2
# e 0 1 2 3
#
# 计算过程：
# i=1 (a), j=1 (a): 'a'=='a' -> dp[1][1] = dp[0][0]+1 = 1
# i=1 (a), j=2 (c): 'a'!='c' -> dp[1][2] = max(dp[0][2],dp[1][1]) = max(0,1) = 1
# i=1 (a), j=3 (e): 'a'!='e' -> dp[1][3] = max(dp[0][3],dp[1][2]) = max(0,1) = 1
#
# i=2 (b), j=1 (a): 'b'!='a' -> dp[2][1] = max(dp[1][1],dp[2][0]) = max(1,0) = 1
# i=2 (b), j=2 (c): 'b'!='c' -> dp[2][2] = max(dp[1][2],dp[2][1]) = max(1,1) = 1
# i=2 (b), j=3 (e): 'b'!='e' -> dp[2][3] = max(dp[1][3],dp[2][2]) = max(1,1) = 1
#
# i=3 (c), j=1 (a): 'c'!='a' -> dp[3][1] = max(dp[2][1],dp[3][0]) = max(1,0) = 1
# i=3 (c), j=2 (c): 'c'=='c' -> dp[3][2] = dp[2][1]+1 = 1+1 = 2
# i=3 (c), j=3 (e): 'c'!='e' -> dp[3][3] = max(dp[2][3],dp[3][2]) = max(1,2) = 2
#
# i=4 (d), j=1 (a): 'd'!='a' -> dp[4][1] = max(dp[3][1],dp[4][0]) = max(1,0) = 1
# i=4 (d), j=2 (c): 'd'!='c' -> dp[4][2] = max(dp[3][2],dp[4][1]) = max(2,1) = 2
# i=4 (d), j=3 (e): 'd'!='e' -> dp[4][3] = max(dp[3][3],dp[4][2]) = max(2,2) = 2
#
# i=5 (e), j=1 (a): 'e'!='a' -> dp[5][1] = max(dp[4][1],dp[5][0]) = max(1,0) = 1
# i=5 (e), j=2 (c): 'e'!='c' -> dp[5][2] = max(dp[4][2],dp[5][1]) = max(2,1) = 2
# i=5 (e), j=3 (e): 'e'=='e' -> dp[5][3] = dp[4][2]+1 = 2+1 = 3
#
# 结果: dp[5][3] = 3，即 "ace"
|
编辑距离
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
输入：word1 = “horse”, word2 = “ros”
输出：3
解释：
horse -> rorse (将 ‘h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’)
rose -> ros (删除 ’e’)
word1 和 word2 由小写英文字母组成
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
from typing import List
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
"""
使用动态规划求编辑距离
思路：
- dp[i][j] 表示将 word1[0:i] 转换为 word2[0:j] 的最少操作数
- 三种操作：
1. 插入：dp[i][j] = dp[i][j-1] + 1（在 word1 后插入 word2[j-1]）
2. 删除：dp[i][j] = dp[i-1][j] + 1（删除 word1[i-1]）
3. 替换：dp[i][j] = dp[i-1][j-1] + 1（将 word1[i-1] 替换为 word2[j-1]）
- 如果 word1[i-1] == word2[j-1]，则不需要操作：dp[i][j] = dp[i-1][j-1]
- 时间 O(m*n)，空间可优化到 O(min(m,n))
例如 word1="horse", word2="ros"：
需要 3 步：horse -> rorse -> rose -> ros
"""
m, n = len(word1), len(word2)
# 初始化 dp 表（多一行一列用于处理空串）
dp = [[0] * (n + 1) for _ in range(m + 1)]
# base case：空串转换
# 将空串转换为 word2，需要 n 次插入
for j in range(n + 1):
dp[0][j] = j
# 将 word1 转换为空串，需要 m 次删除
for i in range(m + 1):
dp[i][0] = i
# 填充 dp 表
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:
# 三种操作取最小值 + 1
dp[i][j] = min(
dp[i - 1][j] + 1, # 删除 word1[i-1]
dp[i][j - 1] + 1, # 插入 word2[j-1]
dp[i - 1][j - 1] + 1 # 替换
)
return dp[m][n]
def minDistance_optimized(self, word1: str, word2: str) -> int:
"""
空间优化版本：只用一行 dp
思路：
- dp[j] 表示将 word1 前 i 个字符转换为 word2 前 j 个字符的最少操作数
- 需要一个变量 prev 记录 dp[i-1][j-1]
- 时间 O(m*n)，空间 O(n)
"""
m, n = len(word1), len(word2)
# 确保 word2 是较短的字符串，用较少的空间
if m < n:
word1, word2 = word2, word1
m, n = n, m
dp = list(range(n + 1))
for i in range(1, m + 1):
prev = dp[0]
dp[0] = i
for j in range(1, n + 1):
temp = dp[j]
if word1[i - 1] == word2[j - 1]:
dp[j] = prev
else:
dp[j] = min(prev, dp[j], dp[j - 1]) + 1
prev = temp
return dp[n]
# 测试用例
assert Solution().minDistance("horse", "ros") == 3
assert Solution().minDistance("intention", "execution") == 5
assert Solution().minDistance("", "") == 0
assert Solution().minDistance("", "abc") == 3
assert Solution().minDistance("abc", "") == 3
assert Solution().minDistance("abc", "abc") == 0
assert Solution().minDistance("abc", "def") == 3
# 手动推导 word1="horse", word2="ros"：
# dp 表 (行: word1, 列: word2)
# "" r o s
# "" 0 1 2 3
# h 1 1 2 3
# o 2 2 2 3
# r 3 2 3 4
# s 4 3 4 3
# e 5 4 5 4
#
# base case:
# dp[0][j] = j: "", "r", "ro", "ros" 分别需要 0,1,2,3 次插入
# dp[i][0] = i: "h", "ho", "hor", "hors", "horse" 分别需要 1,2,3,4,5 次删除
#
# 计算过程：
# i=1 (h):
# j=1 (r): 'h'!='r' -> dp[1][1] = min(dp[0][1],dp[1][0],dp[0][0]) + 1 = min(1,1,0)+1 = 1
# j=2 (o): 'h'!='o' -> dp[1][2] = min(dp[0][2],dp[1][1],dp[0][1]) + 1 = min(2,1,1)+1 = 2
# j=3 (s): 'h'!='s' -> dp[1][3] = min(dp[0][3],dp[1][2],dp[0][2]) + 1 = min(3,2,2)+1 = 3
#
# i=2 (o):
# j=1 (r): 'o'!='r' -> dp[2][1] = min(dp[1][1],dp[2][0],dp[1][0]) + 1 = min(1,2,1)+1 = 2
# j=2 (o): 'o'=='o' -> dp[2][2] = dp[1][1] = 1
# j=3 (s): 'o'!='s' -> dp[2][3] = min(dp[1][3],dp[2][2],dp[1][2]) + 1 = min(3,1,2)+1 = 2... 不对
#
# 继续计算...
# 最终 dp[5][3] = 3
#
# 转换步骤：
# horse -> rorse (将 'h' 替换为 'r')
# rorse -> rose (删除 'r')
# rose -> ros (删除 'e')
|
其他技巧
只出现一次的数字
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
输入：nums = [2,2,1]
输出：1
除了某个元素只出现一次以外，其余每个元素均出现两次
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
from typing import List
class Solution:
def singleNumber(self, nums: List[int]) -> int:
"""
使用异或运算找出只出现一次的数字
思路：
- 异或运算的性质：
1. a ^ a = 0（相同数字异或为0）
2. a ^ 0 = a（任何数字与0异或为本身）
3. 异或满足交换律和结合律
- 将数组中所有数字进行异或
- 出现两次的数字相互抵消为0
- 剩下的就是只出现一次的数字
- 时间 O(n)，空间 O(1)
例如 [2,1,2]：
2 ^ 1 ^ 2 = 2 ^ 2 ^ 1 = 0 ^ 1 = 1
"""
result = 0
for num in nums:
result ^= num
return result
def singleNumber_hash(self, nums: List[int]) -> int:
"""
方法二：使用哈希表（不满足 O(1) 空间要求）
思路：
- 遍历数组，用哈希表记录每个数字出现的次数
- 找出出现次数为1的数字
- 时间 O(n)，空间 O(n)
"""
count = {}
for num in nums:
count[num] = count.get(num, 0) + 1
for num, cnt in count.items():
if cnt == 1:
return num
return -1
# 测试用例
assert Solution().singleNumber([2, 2, 1]) == 1
assert Solution().singleNumber([4, 1, 2, 1, 2]) == 4
assert Solution().singleNumber([1]) == 1
assert Solution().singleNumber([1, 2, 3, 2, 1]) == 3
assert Solution().singleNumber([-1, -1, -2]) == -2
# 手动推导 [2,2,1]：
# result = 0
# result ^= 2 -> result = 0 ^ 2 = 2
# result ^= 2 -> result = 2 ^ 2 = 0
# result ^= 1 -> result = 0 ^ 1 = 1
# 结果: 1
#
# 手动推导 [4,1,2,1,2]：
# result = 0
# result ^= 4 -> result = 4
# result ^= 1 -> result = 4 ^ 1 = 5
# result ^= 2 -> result = 5 ^ 2 = 7
# result ^= 1 -> result = 7 ^ 1 = 6
# result ^= 2 -> result = 6 ^ 2 = 4
# 结果: 4
|
多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
输入：nums = [3,2,3]
输出：3
输入保证数组中一定有一个多数元素。
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
from typing import List
class Solution:
def majorityElement(self, nums: List[int]) -> int:
"""
方法一：摩尔投票法（Boyer-Moore Voting）
思路：
- 多数元素出现次数大于 n/2
- 想象成两两对战，相同则存活，不同则同归于尽
- 最后存活的必然是多数元素
- candidate 记录当前候选者，count 记录票数
- 时间 O(n)，空间 O(1)
"""
candidate = nums[0]
count = 1
for i in range(1, len(nums)):
if nums[i] == candidate:
count += 1
elif count > 0:
count -= 1
else:
candidate = nums[i]
count = 1
return candidate
def majorityElement_hash(self, nums: List[int]) -> int:
"""
方法二：哈希表（不满足 O(1) 空间要求）
思路：
- 统计每个元素出现的次数
- 返回出现次数大于 n/2 的元素
- 时间 O(n)，空间 O(n)
"""
from collections import Counter
count = Counter(nums)
n = len(nums)
for num, cnt in count.items():
if cnt > n // 2:
return num
return -1
def majorityElement_sort(self, nums: List[int]) -> int:
"""
方法三：排序后取中位数（不满足 O(1) 空间要求）
思路：
- 多数元素出现次数大于 n/2
- 排序后，中位数必然是多数元素
- 时间 O(n log n)，空间 O(1)（如果原地排序）
"""
nums.sort()
return nums[len(nums) // 2]
# 测试用例
assert Solution().majorityElement([3, 2, 3]) == 3
assert Solution().majorityElement([2, 2, 1, 1, 1, 2, 2]) == 2
assert Solution().majorityElement([1]) == 1
assert Solution().majorityElement([1, 2, 1]) == 1
assert Solution().majorityElement([1, 1, 2, 2, 2]) == 2
# 手动推导 [2, 2, 1, 1, 1, 2, 2]（n=7，多数元素需出现>3.5次，即至少4次）：
# candidate=2, count=1
# i=1: 2==2, count=2
# i=2: 1!=2, count=1
# i=3: 1!=2, count=0
# i=4: 1!=2, count=0 -> candidate=1, count=1
# i=5: 2!=1, count=0
# i=6: 2!=1, count=0 -> candidate=2, count=1
# 返回 candidate=2
#
# 简化理解：
# [2,2,1,1,1,2,2]
# 2 vs 2 -> 抵消
# 1 vs 1 -> 抵消
# 1 vs 2 -> 不同，1 和 2 抵消？不，这不对...
#
# 重新理解摩尔投票：
# 每个元素出现两次就抵消，由于多数元素出现次数 > n/2
# 最后必然剩下多数元素
#
# [2,2,1,1,1,2,2]
# 步骤：
# 2 vs 2 -> count=0, candidate=无
# 1 -> count=1, candidate=1
# 1 vs 1 -> count=2
# 2 vs 2 -> count=1
# 2 vs ... -> count=0
# 最终 candidate=2
|
颜色分类
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
进阶：你能想出一个仅使用常数空间的一趟扫描算法吗？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
|
from typing import List
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
使用三路划分（Dutch National Flag）原地排序 0, 1, 2
思路：
- 使用三个指针：
- left：0 的边界（[0, left) 都是 0）
- right：2 的边界（(right, n-1] 都是 2）
- i：当前遍历的位置
- 遍历数组，根据 nums[i] 的值交换到对应区域
- 时间 O(n)，空间 O(1)
图解：
[0, 0, 1, 1, 2, 2, ...]
^ ^ ^
left i right
"""
if not nums:
return
n = len(nums)
left = 0 # 0 的右边界
right = n - 1 # 2 的左边界
i = 0
while i <= right:
if nums[i] == 0:
# 交换到 left 区域
nums[left], nums[i] = nums[i], nums[left]
left += 1
i += 1 # 交换后 nums[i] 已经是处理过的，可以 i++
elif nums[i] == 2:
# 交换到 right 区域
# 注意：交换后 nums[i] 变成新的值，需要继续处理，所以 i 不变
nums[right], nums[i] = nums[i], nums[right]
right -= 1
else: # nums[i] == 1
i += 1
def sortColors_counting(self, nums: List[int]) -> None:
"""
方法二：计数排序（两遍扫描）
思路：
- 先统计 0, 1, 2 的个数
- 再按个数重新填充数组
- 时间 O(n)，空间 O(1)
"""
count = [0, 0, 0]
for num in nums:
count[num] += 1
idx = 0
for i in range(3):
for _ in range(count[i]):
nums[idx] = i
idx += 1
# 测试用例
nums1 = [2, 0, 2, 1, 1, 0]
Solution().sortColors(nums1)
assert nums1 == [0, 0, 1, 1, 2, 2]
nums2 = [2, 0, 1]
Solution().sortColors(nums2)
assert nums2 == [0, 1, 2]
nums3 = [0]
Solution().sortColors(nums3)
assert nums3 == [0]
nums4 = [1, 1, 1]
Solution().sortColors(nums4)
assert nums4 == [1, 1, 1]
nums5 = [2, 2, 0, 0, 1, 1]
Solution().sortColors(nums5)
assert nums5 == [0, 0, 1, 1, 2, 2]
# 手动推导 [2,0,2,1,1,0]：
# 初始: left=0, right=5, i=0
# nums = [2, 0, 2, 1, 1, 0]
# ^
# i
#
# i=0: nums[0]=2，交换 nums[0] 和 nums[5]
# nums = [0, 0, 2, 1, 1, 2]
# ^ ^
# right=4 i
#
# i=0: nums[0]=0，交换（自己），left=1, i=1
# nums = [0, 0, 2, 1, 1, 2]
# ^ ^
# left i
#
# i=1: nums[1]=0，交换（自己），left=2, i=2
# nums = [0, 0, 2, 1, 1, 2]
# ^
# i,right
#
# i=2: nums[2]=2，交换 nums[2] 和 nums[4]
# nums = [0, 0, 1, 1, 2, 2]
# ^ ^
# i right
#
# i=2: nums[2]=1，i++ -> i=3
# i=3: nums[3]=1，i++ -> i=4
# i=4: i=4 > right=3，退出
#
# 结果: [0, 0, 1, 1, 2, 2]
|
下一个排列
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
例如，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 = [1,2,3]
输出：[1,3,2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
from typing import List
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
原地修改数组为下一个排列
思路：
1. 从右往左找到第一个降序的位置 i（即 nums[i] < nums[i+1]）
- 这表示存在一个更大的排列
- i 位置是需要被替换的较小数字
2. 从右往左找到第一个大于 nums[i] 的位置 j
- 这是在 i 右侧所有比 nums[i] 大的数中最小的
3. 交换 nums[i] 和 nums[j]
4. 将 i+1 到末尾的部分反转（变成升序，即最小的排列）
例如 [1,2,3,6,5,4]：
- 找到 i=2 (3)，因为 3 < 6
- 找到 j=4 (4)，因为 4 是右侧比 3 大的最小值
- 交换得到 [1,2,4,6,5,3]
- 反转 6,5,3 得到 3,5,6
- 最终 [1,2,4,3,5,6]
"""
n = len(nums)
if n <= 1:
return
# 1. 从右往左找到第一个降序的位置
i = n - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i >= 0:
# 2. 从右往左找到第一个大于 nums[i] 的位置
j = n - 1
while nums[j] <= nums[i]:
j -= 1
# 3. 交换
nums[i], nums[j] = nums[j], nums[i]
# 4. 反转 i+1 到末尾的部分（变成升序）
left, right = i + 1, n - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
# 测试用例
# 测试 [1,2,3]
nums1 = [1, 2, 3]
Solution().nextPermutation(nums1)
assert nums1 == [1, 3, 2]
# 测试 [3,2,1]
nums2 = [3, 2, 1]
Solution().nextPermutation(nums2)
assert nums2 == [1, 2, 3]
# 测试 [1,1,5]
nums3 = [1, 1, 5]
Solution().nextPermutation(nums3)
assert nums3 == [1, 5, 1]
# 测试 [1,2,3,6,5,4]
nums4 = [1, 2, 3, 6, 5, 4]
Solution().nextPermutation(nums4)
assert nums4 == [1, 2, 4, 3, 5, 6]
# 测试 [1,3,2,3]
nums5 = [1, 3, 2, 3]
Solution().nextPermutation(nums5)
assert nums5 == [1, 3, 3, 2]
# 测试单个元素
nums6 = [1]
Solution().nextPermutation(nums6)
assert nums6 == [1]
# 手动推导 [1,2,3]：
# 1. 从右往左找降序位置 i：
# i=2: 3 >= None（越界），i=1
# i=1: 2 < 3，找到！i=1
# 2. 从右往左找第一个大于 nums[1]=2 的位置 j：
# j=2: 3 > 2，找到！j=2
# 3. 交换：交换位置1和2
# [1, 3, 2]
# 4. 反转 i+1=2 到末尾：只有一个元素，无需反转
# 结果：[1, 3, 2]
#
# 手动推导 [3,2,1]：
# 1. 从右往左找降序位置 i：
# i=1: 2 >= 1，继续
# i=0: 3 >= 2，继续
# i=-1: 越界，没有找到降序位置
# 2. 没有找到，整个数组是最大排列
# 3. 反转整个数组
# [1, 2, 3]
# 结果：[1, 2, 3]
|
寻找重复数
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
输入：nums = [1,3,4,2,2]
输出：2
nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次
进阶：
如何证明 nums 中至少存在一个重复的数字?
你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
|
from typing import List
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
"""
方法一：快慢指针（龟兔赛跑）
思路：
- 将数组看成一个链表，nums[i] 表示从节点 i 指向节点 nums[i]
- 由于存在重复数字，必然存在环
- 找到环的入口就是重复的数字
- 时间 O(n)，空间 O(1)
例如 [1,3,4,2,2]：
0 -> 1 -> 3 -> 2 -> 4
^ |
+----+
环的入口是节点 2，即重复的数字是 2
"""
# 第一步：找到相遇点
slow = nums[0]
fast = nums[nums[0]]
while slow != fast:
slow = nums[slow]
fast = nums[nums[fast]]
# 第二步：从起点和相遇点同时出发，相遇点即为环入口
slow = 0
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
def findDuplicate_binary_search(self, nums: List[int]) -> int:
"""
方法二：二分查找（抽屉原理）
思路：
- 数组中数字在 [1, n] 范围内
- 二分查找重复数字可能存在的范围
- 统计 <= mid 的数字个数
- 如果 count > mid，说明重复数字在 [1, mid]
- 否则在 [mid+1, n]
- 时间 O(n log n)，空间 O(1)
抽屉原理：n+1 个物品放到 n 个抽屉里，至少有一个抽屉有两个物品
"""
left, right = 1, len(nums) - 1
while left < right:
mid = (left + right) // 2
# 统计 <= mid 的数字个数
count = sum(1 for num in nums if num <= mid)
if count > mid:
# 重复数字在左半部分
right = mid
else:
# 重复数字在右半部分
left = mid + 1
return left
def findDuplicate_set(self, nums: List[int]) -> int:
"""
方法三：哈希集合（不满足 O(1) 空间要求）
思路：
- 用集合记录已见过的数字
- 遇到重复数字即返回
- 时间 O(n)，空间 O(n)
"""
seen = set()
for num in nums:
if num in seen:
return num
seen.add(num)
return -1
# 测试用例
assert Solution().findDuplicate([1, 3, 4, 2, 2]) == 2
assert Solution().findDuplicate([3, 1, 3, 4, 2]) == 3
assert Solution().findDuplicate([3, 3, 3, 3, 3]) == 3
assert Solution().findDuplicate([1, 1]) == 1
assert Solution().findDuplicate([1, 1, 2]) == 1
assert Solution().findDuplicate([2, 2, 2, 2]) == 2
# 手动推导 [1,3,4,2,2]（方法一快慢指针）：
# 链表结构：
# 0 -> 1 -> 3 -> 2 -> 4
# ^ |
# +----+
#
# 第一步：快慢指针找相遇点
# slow = nums[0] = 1
# fast = nums[nums[0]] = nums[1] = 3
#
# 循环直到相遇：
# slow = nums[slow] = nums[1] = 3
# fast = nums[nums[fast]] = nums[nums[3]] = nums[2] = 4
# slow = 3, fast = 4，不相等
#
# slow = nums[slow] = nums[3] = 2
# fast = nums[nums[fast]] = nums[nums[4]] = nums[2] = 4
# slow = 2, fast = 4，不相等
#
# slow = nums[slow] = nums[2] = 4
# fast = nums[nums[fast]] = nums[nums[4]] = nums[2] = 4
# slow = 4, fast = 4，相遇！
#
# 第二步：找环入口
# slow = 0（从头开始）
# 循环直到相遇：
# slow = nums[slow] = nums[0] = 1
# fast = nums[fast] = nums[4] = 2
# slow = 1, fast = 2，不相等
#
# slow = nums[slow] = nums[1] = 3
# fast = nums[fast] = nums[2] = 4
# slow = 3, fast = 4，不相等
#
# slow = nums[slow] = nums[3] = 2
# fast = nums[fast] = nums[4] = 2
# slow = 2, fast = 2，相遇！返回 2
#
# 结果：重复数字是 2
#
# 手动推导 [3,1,3,4,2]（方法二二分查找）：
# 范围 [1, 4], mid=2
# count = 统计 <= 2 的数字：3,1,4,2 中有 1,2 共2个
# count=2 <= mid=2，重复数字在右半部分，left=3
#
# 范围 [3, 4], mid=3
# count = 统计 <= 3 的数字：3,1,3,4,2 中有 3,1,3,2 共3个
# count=3 > mid=3，重复数字在左半部分，right=3
#
# left=3, right=3，退出，返回 3
#
# 结果：重复数字是 3
|
记录生活