动态规划专题¶
本文件按 6 个核心技术模块 组织，而非按题号。每个模块内由浅入深，相同模块内的变量命名、边界处理、代码结构严格统一，便于形成模式记忆。
第 0 章 · DP 方法论¶
0.1 五步曲（解题流程）¶
对任何一道 DP 题，都按下面五步走：
- 确定 dp 数组与下标含义（状态定义）
- 确定递推公式（状态转移）
- 确定 dp 初始化（边界）
- 确定遍历顺序（保证计算 dp[i] 时依赖项已算好）
- 举例推导（手算一次验证）
一句话总结：DP = 合理的状态表达 + 无环的状态转移 + 正确的边界 + 合法的计算顺序。
0.2 六大模块总览¶
| 模块 | 状态形式 | 统一变量 | 核心转移骨架 | 典型题目 |
|---|---|---|---|---|
| M1 线性 DP | dp[i] |
dp, n |
dp[i] = f(dp[i-1], dp[i-2]) |
爬楼梯、打家劫舍、LIS |
| M2 状态机 DP | dp[i][k] |
dp[i][0/1] |
每个状态独立转移 | 股票系列、乘积最大子数组 |
| M3 背包 DP | dp[i][j] |
dp, i=物品, j=容量 |
dp[i][j] = op(dp[i-1][j], dp[i-1][j-w]+v) |
背包、零钱兑换、单词拆分 |
| M4 双序列 DP | dp[i][j] |
m, n, 原串用 s1[i-1] |
dp[i][j] = f(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) |
LCS、编辑距离 |
| M5 网格 DP | dp[i][j] |
m, n |
同 M4 但 i, j 是坐标 | 不同路径、最小路径和 |
| M6 区间 DP | dp[i][j] |
i, j 为区间端点 | 先枚举长度再枚举起点 | 回文子串、最长回文子序列 |
0.3 边界判断 · +1 决策树 ⭐（最核心的判断）¶
全局原则：非必要不加 1。只有当"空状态"会真的被转移式引用参与计算时，才需要 +1 多开一位。
决策树¶
问题：dp 数组长度应该是 n 还是 n+1 ？
┌─ 第一层：转移式中，dp[0]（或 dp[0][*] / dp[*][0]）
│ 会被右侧引用来参与计算吗？
│
├─ 【是】dp[0] 作为"空状态"真实参与转移 ───→ ✅ 必须 +1
│ · 背包：dp[1][j] = max(dp[0][j], dp[0][j-w]+v)，dp[0] 必须存在
│ · 双序列：dp[1][1] = ... 依赖 dp[0][0]、dp[0][1]、dp[1][0]
│
└─ 【否】转移从 i ≥ 2 起推，dp[0]/dp[1] 只是起点赋值
│
└─ 第二层：状态定义里"前 0 个元素"有合法语义吗？
│
├─ 【有】例：爬楼梯"到第 0 阶 = 1 种" 有意义
│ → 🟡 可加可不加，**统一选不加**（保持模块一致）
│
└─ 【没有】例：LIS"以第 -1 个元素结尾"、
最大子数组"以 -1 位置结尾" 无意义
→ ❌ 禁止 +1
六模块 +1 决策速查表¶
| 模块 | +1 决策 | 判定依据 |
|---|---|---|
| M1 线性 | ❌ 不 +1 | 转移只需 dp[i-1]/dp[i-2]，起点直接赋值 |
| M1 · 746 最小花费 | ⚠ 被动 +1 | 题目要求到达下标 n 的楼顶（在 cost 数组之外），dp 长度天然为 n+1。不是"加空状态" |
| M2 状态机 | ❌ 不 +1 | "第 i 天的状态"或"以 i 结尾"的定义强制 |
| M3 背包 | ✅ 必须 +1 | dp[0][j] = "选 0 件物品" 会被 dp[1][j] 的转移引用 |
| M4 双序列 | ✅ 必须 +1 | dp[0][j] = "空串 vs s2[:j]" 会被 dp[i-1][j-1] 引用 |
| M5 网格 | ❌ 不 +1 | "虚拟第 -1 行" 无物理意义，手动填第一行/列更清晰 |
| M6 区间 | ❌ 不 +1 | i, j 直接是区间端点下标，无"空区间"语义 |
一句话记忆：只有背包和双序列必须 +1，其他模块统一不 +1。
0.4 五个注释标签（区分骨架与装饰）¶
dp[0][j] = j # [关键] 核心边界 —— 删掉就错
dp[0] = 0 # [冗余] Python 默认已是 0，保留仅为强调语义
dp = [inf] * (n + 1) # [哨兵] 为求最小值初始化为极值
for j in range(target, w - 1, -1): # [注意] 遍历顺序是语义的一部分
# [可选] 性能剪枝，不影响正确性
0.5 统一变量命名约定¶
| 模块 | 命名 |
|---|---|
| 线性 DP | dp, n = len(nums), i |
| 状态机 DP | dp[i][0] / dp[i][1]（持股/持币或未买/已卖） |
| 背包 DP | dp[i][j], w=weight, v=value, j=容量 |
| 双序列 DP | dp[i][j], m, n = len(s1), len(s2), 访问原串用 s1[i-1] / s2[j-1] |
| 网格 DP | dp[i][j], m, n = len(grid), len(grid[0]) |
| 区间 DP | dp[i][j], length（外层循环长度）, i（左端点）, j = i + length - 1 |
本文件全部使用二维（或原始维度）DP 数组，不做滚动数组空间优化。理解状态定义比省空间更重要。
第 1 章 · 线性 DP（M1）¶
特征：状态只沿一个维度推进，dp[i] 只依赖前面少数几个状态。
统一命名：dp, n = len(...), i。
+1 决策：❌ 不 +1（全章统一）。dp[i] 永远对应"第 i 个元素相关的状态"（注：746 因题目要求到 n 楼顶而被动 +1，属特例）。
1.1 爬楼梯 · 70¶
爬到第 n 阶楼梯的方法数。每次可爬 1 或 2 阶。
- 状态：
dp[i]= 爬到第 (i+1) 阶的方法数（下标从 0 起算） - 转移：
dp[i] = dp[i-1] + dp[i-2] - 边界：
dp[0] = 1（1 阶：1 种）、dp[1] = 2（2 阶：2 种）
为什么不 +1：转移只用
dp[i-1]和dp[i-2]，dp[0]只作起点赋值、不作为"空状态"参与递推。加不加 1 都能算对，但全章统一不 +1，让dp[i]始终对应一个具体的阶数，避免下标与物理意义错位。
一维空间动态规划
In [215]:
Copied!
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 2: # [关键] n=1/2 直接返回
return n
dp = [0] * n
dp[0] = 1 # [关键] 1 阶：1 种
dp[1] = 2 # [关键] 2 阶：2 种
for i in range(2, n):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[-1]
print(Solution().climbStairs(5)) # 8
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 2: # [关键] n=1/2 直接返回
return n
dp = [0] * n
dp[0] = 1 # [关键] 1 阶：1 种
dp[1] = 2 # [关键] 2 阶：2 种
for i in range(2, n):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[-1]
print(Solution().climbStairs(5)) # 8
8
因为dpi的值取决于前面两个状态dpi_1, dpi_2，因此可以用两个常量进行滚动更新，下面很多题型都可以进行如此的优化！
In [ ]:
Copied!
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 2: # [关键] n=1/2 直接返回
return n
dpi_2, dpi_1 = 1, 2
for i in range(2, n):
dpi = dpi_1 + dpi_2
dpi_2, dpi_1 = dpi_1, dpi
return dpi
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 2: # [关键] n=1/2 直接返回
return n
dpi_2, dpi_1 = 1, 2
for i in range(2, n):
dpi = dpi_1 + dpi_2
dpi_2, dpi_1 = dpi_1, dpi
return dpi
1.2 使用最小花费爬楼梯 · 746¶
每个台阶有代价，每次可走 1 或 2 阶，求到达楼顶（下标 n）的最小代价。
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
- 状态：
dp[i]= 到达第 i 阶的最小花费(包含站在第i阶的花费) - 转移：
dp[i] = min(dp[i-1] + cost[i], dp[i-2] + cost[i]) - 边界：
dp[0] = cost[0]、dp[1] = cost[1]（可从 0 或 1 起步）
关于 +1：这里
dp = [0] * (n+1)的 +1 是被动 +1——题目要求到达下标 n 的楼顶（在 cost 数组之外），dp天然需要索引到 n，所以长度自然就是 n+1。这不是"加空状态"的主动选择，与 70 那种"可加可不加"的情况不同。
In [216]:
Copied!
from typing import List
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
n = len(cost)
dp = [0] * (n + 1) # [注意] 被动 +1：需索引到楼顶 n
cost.append(0)
dp[0] = cost[0]
dp[1] = cost[1]
for i in range(2, n + 1):
dp[i] = min(dp[i - 1] + cost[i], dp[i - 2] + cost[i])
return dp[n]
print(Solution().minCostClimbingStairs([10, 15, 20])) # 15
print(Solution().minCostClimbingStairs([1, 100, 1, 1, 1, 100, 1, 1, 100, 1])) # 6
from typing import List
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
n = len(cost)
dp = [0] * (n + 1) # [注意] 被动 +1：需索引到楼顶 n
cost.append(0)
dp[0] = cost[0]
dp[1] = cost[1]
for i in range(2, n + 1):
dp[i] = min(dp[i - 1] + cost[i], dp[i - 2] + cost[i])
return dp[n]
print(Solution().minCostClimbingStairs([10, 15, 20])) # 15
print(Solution().minCostClimbingStairs([1, 100, 1, 1, 1, 100, 1, 1, 100, 1])) # 6
15 6
1.3 打家劫舍 · 198¶
不能偷相邻两家，求最大金额。
- 状态：
dp[i]= 偷到第 i 家（含或不含）时的最大金额 - 转移：
dp[i] = max(dp[i-1], dp[i-2] + nums[i]) - 边界：
dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])
In [218]:
Copied!
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
dp = [0] * n
dp[0] = nums[0] # [关键] 只有一家时只能偷它
dp[1] = max(nums[0], nums[1]) # [关键] 两家之中选大的
for i in range(2, n):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return dp[-1]
print(Solution().rob([1, 2, 3, 1])) # 4
print(Solution().rob([2, 7, 9, 3, 1])) # 12
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
dp = [0] * n
dp[0] = nums[0] # [关键] 只有一家时只能偷它
dp[1] = max(nums[0], nums[1]) # [关键] 两家之中选大的
for i in range(2, n):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return dp[-1]
print(Solution().rob([1, 2, 3, 1])) # 4
print(Solution().rob([2, 7, 9, 3, 1])) # 12
4 12
In [219]:
Copied!
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
if n == 2:
return max(nums)
dpi_2, dpi_1 = nums[0], max(nums[0], nums[1])
for i in range(2, n):
dpi = max(dpi_1, dpi_2 + nums[i])
dpi_2, dpi_1 = dpi_1, dpi
return dpi
print(Solution().rob([1, 2, 3, 1])) # 4
print(Solution().rob([2, 7, 9, 3, 1])) # 12
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
if n == 2:
return max(nums)
dpi_2, dpi_1 = nums[0], max(nums[0], nums[1])
for i in range(2, n):
dpi = max(dpi_1, dpi_2 + nums[i])
dpi_2, dpi_1 = dpi_1, dpi
return dpi
print(Solution().rob([1, 2, 3, 1])) # 4
print(Solution().rob([2, 7, 9, 3, 1])) # 12
4 12
1.4 打家劫舍 II · 213（环形）¶
房屋排成一圈（首尾相连），不能偷相邻。
- 核心技巧：环形 = 两次线性 DP
- 所有合法解必须满足：要么不选第一个，要么不选最后一个（或者两个都不选）
- 情况 A：偷第一家：
nums[0..n-2] - 情况 B：不偷第一家：
nums[1..n-1]（最后一个可以选，也可以不选） - 所有合法方案必然属于这两类之一，因此最后取两者较大值即可
- 情况 A：偷第一家：
In [176]:
Copied!
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
if n == 2:
return max(nums)
def rob_linear(arr: List[int]) -> int:
m = len(arr)
dp = [0] * m
dp[0] = arr[0]
dp[1] = max(arr[0], arr[1])
for i in range(2, m):
dp[i] = max(dp[i - 1], dp[i - 2] + arr[i])
return dp[-1]
return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))
print(Solution().rob([2, 3, 2])) # 3
print(Solution().rob([1, 2, 3, 1])) # 4
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
if n == 2:
return max(nums)
def rob_linear(arr: List[int]) -> int:
m = len(arr)
dp = [0] * m
dp[0] = arr[0]
dp[1] = max(arr[0], arr[1])
for i in range(2, m):
dp[i] = max(dp[i - 1], dp[i - 2] + arr[i])
return dp[-1]
return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))
print(Solution().rob([2, 3, 2])) # 3
print(Solution().rob([1, 2, 3, 1])) # 4
3 4
1.5 最大子数组和 · 53¶
返回一个具有最大和的连续子数组（至少一个元素）的和。
- 状态：
dp[i]= 以 nums[i] 结尾的最大子数组和（注意是"结尾"不是"前 i 个"） - 转移：
dp[i] = max(nums[i], dp[i-1] + nums[i]) - 边界：
dp[0] = nums[0] - 答案：
max(dp)（不是dp[-1]，因为最大值可能在中间）
为什么禁止 +1："以 i 结尾"的定义里，
dp[-1]= "以 -1 位置结尾" 无物理意义。
In [177]:
Copied!
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
dp = [0] * n
dp[0] = nums[0] # [关键] 起点必填，不能是默认 0
for i in range(1, n):
dp[i] = max(nums[i], dp[i - 1] + nums[i])
return max(dp) # [注意] 答案是所有 dp 的最大值
print(Solution().maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])) # 6
print(Solution().maxSubArray([5, 4, -1, 7, 8])) # 23
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
dp = [0] * n
dp[0] = nums[0] # [关键] 起点必填，不能是默认 0
for i in range(1, n):
dp[i] = max(nums[i], dp[i - 1] + nums[i])
return max(dp) # [注意] 答案是所有 dp 的最大值
print(Solution().maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])) # 6
print(Solution().maxSubArray([5, 4, -1, 7, 8])) # 23
6 23
1.6 杨辉三角 · 118¶
返回前 numRows 行杨辉三角。
- 状态：
dp[i][j]= 第 i 行第 j 列的值 - 转移：
dp[i][j] = dp[i-1][j-1] + dp[i-1][j] - 边界：每行首尾均为 1
In [178]:
Copied!
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
dp = []
for i in range(numRows):
row = [1] * (i + 1) # [关键] 每行首尾设为 1
for j in range(1, i): # [注意] 只填中间位置
row[j] = dp[i - 1][j - 1] + dp[i - 1][j]
dp.append(row)
return dp
print(Solution().generate(5))
# [[1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1]]
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
dp = []
for i in range(numRows):
row = [1] * (i + 1) # [关键] 每行首尾设为 1
for j in range(1, i): # [注意] 只填中间位置
row[j] = dp[i - 1][j - 1] + dp[i - 1][j]
dp.append(row)
return dp
print(Solution().generate(5))
# [[1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1]]
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
1.7 最长递增子序列 · 300¶
给你整数数组 nums，返回最长严格递增子序列的长度。
- 状态：
dp[i]= 以 nums[i] 结尾的最长严格递增子序列长度 - 转移：
dp[i] = max(dp[j] + 1 for j < i if nums[j] < nums[i])，默认dp[i] = 1 - 边界：
dp = [1] * n（每个元素自己至少算长度 1） - 答案：
max(dp)
为什么禁止 +1：同 53，"以 i 结尾"的语义不允许 -1 位置。
In [179]:
Copied!
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
dp = [1] * n # [关键] 每个位置默认至少 1
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
print(Solution().lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])) # 4
print(Solution().lengthOfLIS([0, 1, 0, 3, 2, 3])) # 4
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
dp = [1] * n # [关键] 每个位置默认至少 1
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
print(Solution().lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])) # 4
print(Solution().lengthOfLIS([0, 1, 0, 3, 2, 3])) # 4
4 4
1.7.x 【教学拓展】打印具体 LIS 序列¶
上面只返回了长度。如果要输出其中一条最长递增子序列，需要额外记录每一步从哪里转移过来：
prev[i]= 让dp[i]取得最大值的前驱下标- 最后从最大值位置出发回溯
In [180]:
Copied!
def longest_increasing_subsequence(nums: List[int]) -> List[int]:
if not nums:
return []
n = len(nums)
dp = [1] * n
prev = [-1] * n # [关键] 记录每个 i 的最佳前驱
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i] and dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
prev[i] = j
# 从最长位置回溯
# index = max(range(n), key=lambda k: dp[k]) 在所有索引 0 ~ n-1 中，找到使 dp[k] 最大的那个索引 k
max_len = max(dp)
index = dp.index(max_len)
result = []
while index != -1:
result.append(nums[index])
index = prev[index]
return result[::-1]
print(longest_increasing_subsequence([10, 9, 2, 5, 3, 7, 101, 18]))
# 如 [2, 3, 7, 18] 或 [2, 5, 7, 18]（具体取决于并列选择）
def longest_increasing_subsequence(nums: List[int]) -> List[int]:
if not nums:
return []
n = len(nums)
dp = [1] * n
prev = [-1] * n # [关键] 记录每个 i 的最佳前驱
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i] and dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
prev[i] = j
# 从最长位置回溯
# index = max(range(n), key=lambda k: dp[k]) 在所有索引 0 ~ n-1 中，找到使 dp[k] 最大的那个索引 k
max_len = max(dp)
index = dp.index(max_len)
result = []
while index != -1:
result.append(nums[index])
index = prev[index]
return result[::-1]
print(longest_increasing_subsequence([10, 9, 2, 5, 3, 7, 101, 18]))
# 如 [2, 3, 7, 18] 或 [2, 5, 7, 18]（具体取决于并列选择）
[2, 5, 7, 101]
1.7.y 【教学拓展】贪心 + 二分优化到 O(n log n)¶
LIS 有一个非 DP 解法：维护一个 tails 数组，tails[k] 表示长度为 k+1 的递增子序列的最小末尾。
每个新元素用二分查找替换第一个 ≥ 它的位置，最终 len(tails) 就是答案。
In [181]:
Copied!
from bisect import bisect_left
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
tails = []
for x in nums:
idx = bisect_left(tails, x)
if idx == len(tails):
tails.append(x) # [关键] x 严格大于当前所有 tail
else:
tails[idx] = x # [关键] 贪心：让该长度的结尾更小
return len(tails)
print(Solution().lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])) # 4
from bisect import bisect_left
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
tails = []
for x in nums:
idx = bisect_left(tails, x)
if idx == len(tails):
tails.append(x) # [关键] x 严格大于当前所有 tail
else:
tails[idx] = x # [关键] 贪心：让该长度的结尾更小
return len(tails)
print(Solution().lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])) # 4
4
1.8 最长有效括号 · 32¶
给你一个只包含 ( 和 ) 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
- 状态：
dp[i]= 以下标 i 结尾的最长有效括号长度（结尾必须是)） - 转移：只有当
s[i] == ')'时才可能非零，分两种配对情形：- 情形 A：
s[i-1] == '('→dp[i] = dp[i-2] + 2 - 情形 B：
s[i-1] == ')'且s[i - dp[i-1] - 1] == '('→dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]
- 情形 A：
- 边界：
dp = [0] * n - 答案：
max(dp)
In [182]:
Copied!
class Solution:
def longestValidParentheses(self, s: str) -> int:
n = len(s)
if n < 2:
return 0
dp = [0] * n # [冗余] 默认即 0，写出仅为强调"未匹配 = 0"
for i in range(1, n):
if s[i] == ')':
if s[i - 1] == '(':
# 情形 A：...()
dp[i] = (dp[i - 2] if i >= 2 else 0) + 2
else:
# 情形 B：...))，尝试跳过已匹配段
prev_len = dp[i - 1]
match_idx = i - prev_len - 1
if match_idx >= 0 and s[match_idx] == '(':
dp[i] = prev_len + 2 + (dp[match_idx - 1] if match_idx >= 1 else 0)
return max(dp)
print(Solution().longestValidParentheses("(()")) # 2
print(Solution().longestValidParentheses(")()())")) # 4
print(Solution().longestValidParentheses("")) # 0
class Solution:
def longestValidParentheses(self, s: str) -> int:
n = len(s)
if n < 2:
return 0
dp = [0] * n # [冗余] 默认即 0，写出仅为强调"未匹配 = 0"
for i in range(1, n):
if s[i] == ')':
if s[i - 1] == '(':
# 情形 A：...()
dp[i] = (dp[i - 2] if i >= 2 else 0) + 2
else:
# 情形 B：...))，尝试跳过已匹配段
prev_len = dp[i - 1]
match_idx = i - prev_len - 1
if match_idx >= 0 and s[match_idx] == '(':
dp[i] = prev_len + 2 + (dp[match_idx - 1] if match_idx >= 1 else 0)
return max(dp)
print(Solution().longestValidParentheses("(()")) # 2
print(Solution().longestValidParentheses(")()())")) # 4
print(Solution().longestValidParentheses("")) # 0
2 4 0
第 2 章 · 状态机 DP（M2）¶
特征：在每一步不仅"做或不做"，还要记录多个状态（持股 / 持币 / 冷冻），每个状态独立转移。
统一命名：dp[i][0] / dp[i][1]。通常：
dp[i][0]= 第 i 天结束时未持有股票的最大利润dp[i][1]= 第 i 天结束时持有股票的最大利润
+1 决策：❌ 不 +1。"第 i 天的状态"无"第 -1 天"概念。
边界：dp[0][0] = 0（第一天不买，利润 0），dp[0][1] = -prices[0]（第一天买入）。
2.1 乘积最大子数组 · 152¶
找出数组中乘积最大的非空连续子数组。
- 为什么需要两个状态：负数乘负数变正，所以当前的最小值也可能变成下一步的最大值
- 状态：
fmax[i]= 以 nums[i] 结尾的最大乘积fmin[i]= 以 nums[i] 结尾的最小乘积
- 转移：
fmax[i] = max(nums[i], fmax[i-1]*nums[i], fmin[i-1]*nums[i])，同理fmin[i] - 答案：
max(fmax)
In [183]:
Copied!
class Solution:
def maxProduct(self, nums: List[int]) -> int:
n = len(nums)
fmax = [0] * n
fmin = [0] * n
fmax[0] = fmin[0] = nums[0] # [关键] 起点同时作为最大最小
for i in range(1, n):
x = nums[i]
fmax[i] = max(x, fmax[i - 1] * x, fmin[i - 1] * x)
fmin[i] = min(x, fmax[i - 1] * x, fmin[i - 1] * x)
return max(fmax)
print(Solution().maxProduct([2, 3, -2, 4])) # 6
print(Solution().maxProduct([-2, 0, -1])) # 0
print(Solution().maxProduct([-2, 3, -4])) # 24
class Solution:
def maxProduct(self, nums: List[int]) -> int:
n = len(nums)
fmax = [0] * n
fmin = [0] * n
fmax[0] = fmin[0] = nums[0] # [关键] 起点同时作为最大最小
for i in range(1, n):
x = nums[i]
fmax[i] = max(x, fmax[i - 1] * x, fmin[i - 1] * x)
fmin[i] = min(x, fmax[i - 1] * x, fmin[i - 1] * x)
return max(fmax)
print(Solution().maxProduct([2, 3, -2, 4])) # 6
print(Solution().maxProduct([-2, 0, -1])) # 0
print(Solution().maxProduct([-2, 3, -4])) # 24
6 0 24
2.2 买卖股票的最佳时机 · 121（只能交易一次）¶
只能买卖一次，求最大利润。
- 状态：
dp[i][0]= 第 i 天结束不持股的最大利润(不持股”说明：要么一直没买要么已经买了并卖掉了)；dp[i][1]= 到第 i 天为止，选择某一天买入后，账户剩余现金的最大值（在只能交易一次的情况下：相当于持股的成本）
- 转移（关键：只能买一次，所以从持币转入持股时利润是
-prices[i]）：dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])；- 表达含义为：第i天不持股的利润 = max（第i-1天的卖出利润， 第i天选择卖出的利润）
dp[i][1] = max(dp[i-1][1], -prices[i])；- 表达含义为：第i天持股的收益（相当于持股的成本（负数）） = max（第i-1天的买入的成本（负数）， 第i天选择买入的成本（负数））
- 边界：
dp[0][0] = 0，dp[0][1] = -prices[0]
In [184]:
Copied!
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
dp = [[0, 0] for _ in range(n)]
dp[0][0] = 0 # [冗余] 默认即 0
dp[0][1] = -prices[0] # [关键] 第一天买入记为 -price
for i in range(1, n):
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = max(dp[i - 1][1], -prices[i]) # [注意] 一次交易：买入不累加历史
return dp[n - 1][0]
print(Solution().maxProfit([7, 1, 5, 3, 6, 4])) # 5
print(Solution().maxProfit([7, 6, 4, 3, 1])) # 0
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
dp = [[0, 0] for _ in range(n)]
dp[0][0] = 0 # [冗余] 默认即 0
dp[0][1] = -prices[0] # [关键] 第一天买入记为 -price
for i in range(1, n):
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = max(dp[i - 1][1], -prices[i]) # [注意] 一次交易：买入不累加历史
return dp[n - 1][0]
print(Solution().maxProfit([7, 1, 5, 3, 6, 4])) # 5
print(Solution().maxProfit([7, 6, 4, 3, 1])) # 0
5 0
简化思路：
遍历价格时，维护“到目前为止最低买入价”和“当前最大利润”。
因为只允许买卖一次，所以利润只取“今天卖出”与“历史最低买入”之间的差值即可。
In [185]:
Copied!
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
min_price = float('inf')
max_profit = 0
for p in prices:
min_price = min(min_price, p)
max_profit = max(max_profit, p - min_price)
return max_profit
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
min_price = float('inf')
max_profit = 0
for p in prices:
min_price = min(min_price, p)
max_profit = max(max_profit, p - min_price)
return max_profit
2.3 买卖股票的最佳时机 II · 122（可交易多次）¶
可以无限次买卖（但必须先卖再买），求最大利润。
与 121 的唯一差别：从持币转入持股时，要累加历史利润：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])；- 表达含义为：第i天不持股的利润 = max（第i-1天的卖出利润， 第i天选择卖出的利润）
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])；- 表达含义为：第i天持股的收益（相当于持股的成本（负数）） = max（第i-1天的买入的成本（负数）， 历史利润 + 第i天选择买入的成本（负数））
In [186]:
Copied!
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
dp = [[0, 0] for _ in range(n)]
dp[0][1] = -prices[0]
for i in range(1, n):
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]) # [注意] 多次交易：累加历史
return dp[n - 1][0]
print(Solution().maxProfit([7, 1, 5, 3, 6, 4])) # 7
print(Solution().maxProfit([1, 2, 3, 4, 5])) # 4
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
dp = [[0, 0] for _ in range(n)]
dp[0][1] = -prices[0]
for i in range(1, n):
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]) # [注意] 多次交易：累加历史
return dp[n - 1][0]
print(Solution().maxProfit([7, 1, 5, 3, 6, 4])) # 7
print(Solution().maxProfit([1, 2, 3, 4, 5])) # 4
7 4
思路是贪心：
只要今天价格比昨天高，就把这段上涨差值加进利润。
因为多次交易没有限制，所以一段连续上涨可以拆成若干次“低买高卖”，总收益等于所有正差分之和。
In [187]:
Copied!
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i - 1]:
profit += prices[i] - prices[i - 1]
return profit
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i - 1]:
profit += prices[i] - prices[i - 1]
return profit
2.4 含冷冻期的股票 · 309¶
卖出后要冷冻 1 天（第 i 天卖出，第 i+1 天不能买入）,可购买多次
与 122 的唯一差别：买入的来源不是 dp[i-1][0]，而是 dp[i-2][0]：
dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
边界：i=0 时没有 dp[-2]，需要单独处理 dp[1][1] = max(dp[0][1], -prices[1])。
In [188]:
Copied!
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
if n < 2:
return 0
dp = [[0, 0] for _ in range(n)]
dp[0][1] = -prices[0]
dp[1][0] = max(dp[0][0], dp[0][1] + prices[1])
dp[1][1] = max(dp[0][1], -prices[1]) # [关键] i=1 无 i-2，单独处理
for i in range(2, n):
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = max(dp[i - 1][1], dp[i - 2][0] - prices[i]) # [注意] 冷冻期
return dp[n - 1][0]
print(Solution().maxProfit([1, 2, 3, 0, 2])) # 3
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
if n < 2:
return 0
dp = [[0, 0] for _ in range(n)]
dp[0][1] = -prices[0]
dp[1][0] = max(dp[0][0], dp[0][1] + prices[1])
dp[1][1] = max(dp[0][1], -prices[1]) # [关键] i=1 无 i-2，单独处理
for i in range(2, n):
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = max(dp[i - 1][1], dp[i - 2][0] - prices[i]) # [注意] 冷冻期
return dp[n - 1][0]
print(Solution().maxProfit([1, 2, 3, 0, 2])) # 3
3
In [189]:
Copied!
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
n = len(prices)
dp = [[0, 0] for _ in range(n)]
dp[0][1] = -prices[0]
for i in range(1, n):
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee) # [注意] 卖出扣手续费
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
return dp[n - 1][0]
print(Solution().maxProfit([1, 3, 2, 8, 4, 9], fee=2)) # 8
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
n = len(prices)
dp = [[0, 0] for _ in range(n)]
dp[0][1] = -prices[0]
for i in range(1, n):
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee) # [注意] 卖出扣手续费
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
return dp[n - 1][0]
print(Solution().maxProfit([1, 3, 2, 8, 4, 9], fee=2)) # 8
8
简洁思路：不要频繁切碎上涨段；要把能合并的上涨尽量合并成一笔交易，只在净收益足够覆盖手续费时才结算
buy 表示“当前这笔潜在交易的最低总成本（买入价 + fee）”；
每当 p > buy 时，就完成一笔交易，利润为 p - buy，其中 fee 已经被扣除一次；
卖出后将 buy 重置为当前价格 p，用于承接后续上涨，从而避免把一段上涨拆成多次交易（避免重复扣 fee）；
若出现更低的有效买点（p + fee < buy），则更新 buy = p + fee，表示用更低的“含手续费成本”重新定义交易起点。
In [190]:
Copied!
from typing import List
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
if not prices:
return 0
buy = prices[0] + fee # 这表示“有效买入成本”
profit = 0
for p in prices[1:]:
if p + fee < buy:
# 当前价格更适合作为新的买点
buy = p + fee
elif p > buy:
# 现在卖出有利可图
profit += p - buy
# 卖完以后，相当于重新把买点抬到当前价
# 这样如果后面继续涨，可以继续吃上涨段
buy = p
return profit
print(Solution().maxProfit([1, 3, 2, 8, 4, 9], fee=2)) # 8
print(Solution().maxProfit([1, 4, 8, 16], fee=2)) # 13
from typing import List
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
if not prices:
return 0
buy = prices[0] + fee # 这表示“有效买入成本”
profit = 0
for p in prices[1:]:
if p + fee < buy:
# 当前价格更适合作为新的买点
buy = p + fee
elif p > buy:
# 现在卖出有利可图
profit += p - buy
# 卖完以后，相当于重新把买点抬到当前价
# 这样如果后面继续涨，可以继续吃上涨段
buy = p
return profit
print(Solution().maxProfit([1, 3, 2, 8, 4, 9], fee=2)) # 8
print(Solution().maxProfit([1, 4, 8, 16], fee=2)) # 13
8 13
第 3 章 · 背包 DP（M3）¶
3.0 背包基础理论¶
核心问题：从若干物品中选或不选，满足约束（容量/和）下求最值、方案数或可达性。
两种类型：
- 0/1 背包：每件物品最多选一次
- 完全背包：每件物品可无限次选
+1 决策：✅ 必须 +1。一维 dp[0] 代表"容量 0 的答案"，会被转移 dp[j] = op(dp[j], dp[j-w]) 在 j == w 时真实引用。
3.0.1 一维三模板（最核心的记忆点）¶
按问题类型对应三种遍历顺序，选错就出错：
完整模板表（整合版）
| 编号 | 类型 | 物品是否复用 | 顺序敏感性 | 外层 | 内层 | 容量方向 | 结构自由度 | 典型问题 |
|---|---|---|---|---|---|---|---|---|
| A | 0/1 背包 | 否 | 天然无序（子集） | 物品 | 容量 | 倒序 | 锁死（唯一写法） | 子集和、分割等和子集、Target Sum、最后一块石头的重量 II |
| B | 完全背包 · 组合/最值/可达 | 是 | 不区分顺序 | 物品 | 容量 | 正序 | 与 C 可切换 | 零钱兑换（最少硬币）、零钱兑换 II（组合数）、完全平方数 |
| C | 完全背包 · 排列 | 是 | 区分顺序 | 容量 | 物品 | 正序 | 必须先容量后物品 | 组合总和 IV、单词拆分（Word Break） |
关键说明：
- 0/1 背包锁死唯一写法：必须"外层物品 + 内层容量倒序"，这是 0/1 语义下不可拆分的共生结构。外层物品保证 DP 状态维护"前 k 件"的前缀语义，内层倒序保证引入第 k 件时
dp[j-w[k]]仍停留在前 k-1 件的状态。若把容量放到外层（无论正序倒序），状态语义直接崩坏，根本算不出正确结果。 - 0/1 背包无排列版：每件物品至多选一次，"子集"本身就是无序概念。
- 多重背包不独立：通过二进制拆分归并到 A，或通过单调队列优化归并到 B/C。
统一理解（分层版）
背包 DP 的循环结构由两个正交维度决定，分别对应两个独立的机关：
维度一：容量遍历方向 → 控制"物品能否复用"
- 倒序：
dp[j-w]读到的是本轮物品尚未加入前的状态 → 每件物品至多贡献一次 → 0/1 背包 - 正序：
dp[j-w]可能已经包含当前物品 → 等价于无限次使用 → 完全背包
维度二：循环嵌套顺序 → 控制"结果是否区分顺序"
- 外层物品 + 内层容量：每件物品一次性处理完再切下一件，同一组合无论走哪条转移路径都被归为一种 → 组合语义
- 外层容量 + 内层物品：每到一个容量都重新枚举所有物品，同一组物品的不同先后次序被分别计入 → 排列语义
两维度交叉得到的三种模板
- A = 不复用 + 无序：外物品 · 内容量 · 倒序 || 额外说明，外容量 · 内物品 · 倒叙无意义，只能计算固定容量下的最大最小单一物品价值
- B = 复用 + 无序：外物品 · 内容量 · 正序
- C = 复用 + 有序：外容量 · 内物品 · 正序
一句话口诀¶
倒序防复用，外层定顺序；0/1 锁死"外物品 + 倒容量"，完全背包放开内外层自由切换组合与排列。
本章 7 道题全部落在这张表里：
| 题号 | 题目 | 模板 |
|---|---|---|
| 416 分割等和子集 | 0/1 · 可达 | A |
| 494 目标和 | 0/1 · 方案数 | A |
| 322 零钱兑换 | 完全 · 最少 | B |
| 518 零钱兑换 II | 完全 · 组合数 | B |
| 279 完全平方数 | 完全 · 最少 | B |
| 139 单词拆分 | 完全 · 可达 | C |
| 377 组合总和 IV | 完全 · 排列数 | C |
3.0.2 为什么 0/1 要"先物品 + 倒序"？推导全流程 ⭐¶
这是整章最需要真正理解的部分。从二维出发，一步步推到一维。
第 1 步 · 二维公式是什么¶
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)
两个选项：
- 不选第 i 件：答案等于
dp[i-1][j]（上一行同列） - 选第 i 件：答案等于
dp[i-1][j-w] + v（上一行左侧某列 + 当前物品价值）
关键观察：计算 dp[i][j] 只依赖上一行 dp[i-1][...]。所以只需要一行数组就够了——新值直接覆盖旧值，每轮物品更新一次。
第 2 步 · 压缩记号¶
把一维数组也记作 dp[j]。在本轮物品 i 更新前，dp[j] 代表旧值 dp[i-1][j]；更新后代表新值 dp[i][j]。转移变成：
dp[j] = max(dp[j], dp[j-w] + v)
但这里产生一个问题：等号右侧的 dp[j-w] 应该读"旧值"还是"新值"？
二维公式要求的是 dp[i-1][j-w]——也就是旧值。所以必须设计遍历顺序，让 dp[j-w] 在被读取时还没被本轮物品更新过。
第 3 步 · 走一遍"正序"，看它为什么错¶
设：物品 w=2, v=3，容量上限 W=5，初始 dp = [0, 0, 0, 0, 0, 0]
正序 j: 2 → 3 → 4 → 5
j=2: dp[2] = max(dp[2], dp[0] + 3) = max(0, 0 + 3) = 3 ✓
j=3: dp[3] = max(dp[3], dp[1] + 3) = max(0, 0 + 3) = 3 ✓
j=4: dp[4] = max(dp[4], dp[2] + 3) = max(0, 3 + 3) = 6 ✗
^^^^^
dp[2] 刚刚被本轮更新为 3！
j=5: dp[5] = max(dp[5], dp[3] + 3) = max(0, 3 + 3) = 6 ✗
错在哪：j=4 读 dp[2] 时，读到的是本轮刚更新的 3——意味着"放了一件 w=2 的物品，再在容量 4 时又放一件"，同一件物品被使用了两次。违反 0/1 规则。
第 4 步 · 走一遍"倒序"，看它为什么对¶
同样数据，倒序 j: 5 → 4 → 3 → 2
j=5: dp[5] = max(dp[5], dp[3] + 3) = max(0, 0 + 3) = 3
^^^^^
dp[3] 尚未被本轮更新，还是旧值 0
j=4: dp[4] = max(dp[4], dp[2] + 3) = max(0, 0 + 3) = 3
j=3: dp[3] = max(dp[3], dp[1] + 3) = max(0, 0 + 3) = 3
j=2: dp[2] = max(dp[2], dp[0] + 3) = max(0, 0 + 3) = 3
最终 dp = [0, 0, 3, 3, 3, 3]。每个 j≥2 都只放一件 w=2 的物品，恰好获得价值 3。
对在哪：从大到小更新时，dp[j-w] 永远在当前 j 的左边（尚未访问区），仍然是"本轮物品到来之前"的旧值——正是二维公式里要求的 dp[i-1][j-w]。
第 5 步 · 为什么必须"先物品"？¶
如果倒过来"先容量、后物品"：
for j in range(1, W + 1):
for num in nums:
if j >= num:
dp[j] = max(dp[j], dp[j - num] + v[num])
同一个 j 下，会依次尝试所有物品——相当于"容量 j 允许任意物品组合反复参与"，语义退化为"允许当前选择与历史选择叠加"，这是完全背包的行为（甚至排列数行为），不再是 0/1。
所以 0/1 必须：
- 先物品（外层）：让每件物品成为独立的"决策轮次"，只被看到一次
- 倒序容量（内层）：让
dp[j-w]不被本轮污染
3.0.3 完全背包为什么"正序"？¶
完全背包允许物品重复使用——刚好与 0/1 相反：
- 用"正序容量"让
dp[j-w]故意被本轮更新过，等同于二维公式里的dp[i][j-w]（当前行，允许再次使用当前物品） - 仍然"先物品"，保证一件物品的"可重复效果"被固化在其自己的一轮内
完全背包的"排列数"版本（377）要求顺序敏感，同一容量 dp[j] 要综合所有可能的"最后一件物品"——必须 先容量后物品，让同一容量下每件物品都有机会作为"最后一步"被算入。
3.0.4 一维 vs 二维的选择¶
本章全部采用一维作为主实现。两道 0/1 题（416、494）会额外附一个二维对照版本，帮助你把 "二维 → 一维压缩" 的映射看得更清楚。完全背包 5 题只给一维。
3.1 分割等和子集 · 416（0/1 · 可达 · 模板 A）¶
判断数组能否分成两个元素和相等的子集。
- 转化：
sum(nums)必为偶数，问题等价于"能否选若干元素和为sum/2" - 状态：
dp[j]= 能否从 nums 中选若干数字凑出和 j（bool） - 转移：
dp[j] = dp[j] or dp[j - num] - 边界：
dp[0] = True（空集凑 0） - 遍历：模板 A · 先物品、倒序容量
In [191]:
Copied!
class Solution:
def canPartition(self, nums: List[int]) -> bool:
total = sum(nums)
if total % 2:
return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True # [关键] 容量 0 可达（空集）
for num in nums: # [注意] 模板 A：先物品
for j in range(target, num - 1, -1): # [注意] 倒序 —— 防重复使用
dp[j] = dp[j] or dp[j - num]
return dp[target]
print(Solution().canPartition([1, 5, 11, 5])) # True
print(Solution().canPartition([1, 2, 3, 5])) # False
class Solution:
def canPartition(self, nums: List[int]) -> bool:
total = sum(nums)
if total % 2:
return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True # [关键] 容量 0 可达（空集）
for num in nums: # [注意] 模板 A：先物品
for j in range(target, num - 1, -1): # [注意] 倒序 —— 防重复使用
dp[j] = dp[j] or dp[j - num]
return dp[target]
print(Solution().canPartition([1, 5, 11, 5])) # True
print(Solution().canPartition([1, 2, 3, 5])) # False
True False
3.1.x 【教学对照】416 的二维写法¶
展示"二维如何压缩成一维"的直接映射：
- 二维里显式写了
dp[i-1][j]和dp[i-1][j-w] - 一维里省略物品维度，靠倒序保持
dp[j-w]读到的是"上一行"的值
In [192]:
Copied!
class SolutionTwoDim:
def canPartition(self, nums: List[int]) -> bool:
total = sum(nums)
if total % 2:
return False
target = total // 2
n = len(nums)
dp = [[False] * (target + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = True # [关键] 任意行 j=0 可达
for i in range(1, n + 1):
w = nums[i - 1]
for j in range(target + 1):
if j < w:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - w]
return dp[n][target]
print(SolutionTwoDim().canPartition([1, 5, 11, 5])) # True
class SolutionTwoDim:
def canPartition(self, nums: List[int]) -> bool:
total = sum(nums)
if total % 2:
return False
target = total // 2
n = len(nums)
dp = [[False] * (target + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = True # [关键] 任意行 j=0 可达
for i in range(1, n + 1):
w = nums[i - 1]
for j in range(target + 1):
if j < w:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - w]
return dp[n][target]
print(SolutionTwoDim().canPartition([1, 5, 11, 5])) # True
True
3.2 目标和 · 494（0/1 · 方案数 · 模板 A）¶
给定数组和目标 target，每个元素前加 + 或 -，问有多少种表达式等于 target。
- 转化：设正号集合和为 P、负号集合和为 N，
P - N = target, P + N = sum→P = (sum + target) / 2。问题变为"0/1 背包凑和 P 的方案数" - 状态：
dp[j]= 凑出和 j 的方案数 - 转移：
dp[j] += dp[j - num]（方案数累加） - 边界：
dp[0] = 1（空集凑 0 算 1 种） - 遍历：模板 A · 先物品、倒序容量
In [193]:
Copied!
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
s = sum(nums)
# [注意] 无解前置检查：(s+target) 必须为偶数且非负
if (s + target) % 2 != 0 or abs(target) > s:
return 0
P = (s + target) // 2
dp = [0] * (P + 1)
dp[0] = 1 # [关键] 空集凑 0 = 1 种方案
for num in nums: # [注意] 模板 A：先物品
for j in range(P, num - 1, -1): # [注意] 倒序
dp[j] += dp[j - num]
return dp[P]
print(Solution().findTargetSumWays([1, 1, 1, 1, 1], target=3)) # 5
print(Solution().findTargetSumWays([1], target=1)) # 1
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
s = sum(nums)
# [注意] 无解前置检查：(s+target) 必须为偶数且非负
if (s + target) % 2 != 0 or abs(target) > s:
return 0
P = (s + target) // 2
dp = [0] * (P + 1)
dp[0] = 1 # [关键] 空集凑 0 = 1 种方案
for num in nums: # [注意] 模板 A：先物品
for j in range(P, num - 1, -1): # [注意] 倒序
dp[j] += dp[j - num]
return dp[P]
print(Solution().findTargetSumWays([1, 1, 1, 1, 1], target=3)) # 5
print(Solution().findTargetSumWays([1], target=1)) # 1
5 1
3.2.x 【教学对照】494 的二维写法¶
与 416 同构（都是 0/1 背包），差别仅在"方案数累加"而非"布尔或"。
In [194]:
Copied!
class SolutionTwoDim:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
s = sum(nums)
if (s + target) % 2 != 0 or abs(target) > s:
return 0
P = (s + target) // 2
n = len(nums)
dp = [[0] * (P + 1) for _ in range(n + 1)]
dp[0][0] = 1 # [关键] 空集凑 0
for i in range(1, n + 1):
w = nums[i - 1]
for j in range(P + 1):
if j < w:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - w]
return dp[n][P]
print(SolutionTwoDim().findTargetSumWays([1, 1, 1, 1, 1], target=3)) # 5
class SolutionTwoDim:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
s = sum(nums)
if (s + target) % 2 != 0 or abs(target) > s:
return 0
P = (s + target) // 2
n = len(nums)
dp = [[0] * (P + 1) for _ in range(n + 1)]
dp[0][0] = 1 # [关键] 空集凑 0
for i in range(1, n + 1):
w = nums[i - 1]
for j in range(P + 1):
if j < w:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - w]
return dp[n][P]
print(SolutionTwoDim().findTargetSumWays([1, 1, 1, 1, 1], target=3)) # 5
5
3.3 零钱兑换 · 322（完全 · 最少物品数 · 模板 B）¶
用 coins 凑出 amount，求最少硬币数；不能凑出返回 -1。
- 状态：
dp[j]= 凑出金额 j 所需最少硬币数 - 转移：
dp[j] = min(dp[j], dp[j - c] + 1) - 边界：
dp[0] = 0，其余初始化为amount + 1（哨兵，任何真实答案都 ≤ amount） - 遍历：模板 B · 先物品、正序容量（允许同一硬币重复使用）
In [195]:
Copied!
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
INF = amount + 1 # [哨兵] 任意合法答案都 ≤ amount
dp = [INF] * (amount + 1)
dp[0] = 0 # [关键] 凑 0 需 0 枚
for c in coins: # [注意] 模板 B：先物品
for j in range(c, amount + 1): # [注意] 正序 —— 允许重复使用
dp[j] = min(dp[j], dp[j - c] + 1)
return dp[amount] if dp[amount] != INF else -1
print(Solution().coinChange([10, 1, 2, 5], amount=11)) # 2
print(Solution().coinChange([2], amount=3)) # -1
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
INF = amount + 1 # [哨兵] 任意合法答案都 ≤ amount
dp = [INF] * (amount + 1)
dp[0] = 0 # [关键] 凑 0 需 0 枚
for c in coins: # [注意] 模板 B：先物品
for j in range(c, amount + 1): # [注意] 正序 —— 允许重复使用
dp[j] = min(dp[j], dp[j - c] + 1)
return dp[amount] if dp[amount] != INF else -1
print(Solution().coinChange([10, 1, 2, 5], amount=11)) # 2
print(Solution().coinChange([2], amount=3)) # -1
2 -1
3.4 零钱兑换 II · 518（完全 · 组合数 · 模板 B）¶
用 coins 凑出 amount，求组合数（不分顺序，[1,2,2] 和 [2,1,2] 算同一种）。
- 状态：
dp[j]= 凑出 j 的组合数 - 转移：
dp[j] += dp[j - c] - 边界：
dp[0] = 1（凑 0 算"什么都不选"1 种方案） - 遍历：模板 B · 先物品、正序容量
- 注意：顺序不能换！外层若变"先容量"会变成排列数（参见 377）
In [196]:
Copied!
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0] * (amount + 1)
dp[0] = 1 # [关键] 凑 0 是 1 种
for c in coins: # [注意] 必须先物品（否则变排列）
for j in range(c, amount + 1): # [注意] 正序
dp[j] += dp[j - c]
return dp[amount]
print(Solution().change(amount=5, coins=[1, 2, 5])) # 4
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0] * (amount + 1)
dp[0] = 1 # [关键] 凑 0 是 1 种
for c in coins: # [注意] 必须先物品（否则变排列）
for j in range(c, amount + 1): # [注意] 正序
dp[j] += dp[j - c]
return dp[amount]
print(Solution().change(amount=5, coins=[1, 2, 5])) # 4
4
3.5 完全平方数 · 279（完全 · 最少物品数 · 模板 B）¶
给你一个整数 n，返回和为 n 的完全平方数的最少数量。
- 物品集合：所有
k² ≤ n的完全平方数 - 与 322 零钱兑换完全同构（只是物品集合是预生成的平方数）
- 遍历：模板 B · 先物品、正序容量
In [197]:
Copied!
class Solution:
def numSquares(self, n: int) -> int:
# 预处理：所有 ≤ n 的完全平方数
squares = []
k = 1
while k * k <= n:
squares.append(k * k)
k += 1
dp = [n + 1] * (n + 1) # [哨兵] 任意合法答案都 ≤ n
dp[0] = 0 # [关键] 凑 0 需 0 个
for s in squares: # [注意] 模板 B：先物品
for j in range(s, n + 1): # [注意] 正序
dp[j] = min(dp[j], dp[j - s] + 1)
return dp[n]
print(Solution().numSquares(12)) # 3 (4+4+4)
print(Solution().numSquares(13)) # 2 (4+9)
class Solution:
def numSquares(self, n: int) -> int:
# 预处理：所有 ≤ n 的完全平方数
squares = []
k = 1
while k * k <= n:
squares.append(k * k)
k += 1
dp = [n + 1] * (n + 1) # [哨兵] 任意合法答案都 ≤ n
dp[0] = 0 # [关键] 凑 0 需 0 个
for s in squares: # [注意] 模板 B：先物品
for j in range(s, n + 1): # [注意] 正序
dp[j] = min(dp[j], dp[j - s] + 1)
return dp[n]
print(Solution().numSquares(12)) # 3 (4+4+4)
print(Solution().numSquares(13)) # 2 (4+9)
3 2
3.6 单词拆分 · 139（完全 · 可达 · 模板 B 变体）¶
给定字符串 s 和字典 wordDict，判断 s 能否由字典中的单词拼接而成（单词可重复使用）。
- 状态：
dp[j]= s[:j] 能否被拼接（bool） - 转移：对每个 j，枚举所有单词 w，若
j >= len(w)且s[j - len(w):j] == w且dp[j - len(w)]，则dp[j] = True - 边界：
dp[0] = True（空串可达） - 遍历：模板 B 的变体 · 这里外层是容量 j（从左到右扫字符串前缀），内层是"物品"（字典单词）。因为"物品"是变长字符串而非数值，以 j 作为前缀终点来匹配更自然。仍属完全背包思想（同一单词可多次使用）
In [198]:
Copied!
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
word_set = set(wordDict) # [可选] 转 set 加速查找
dp = [False] * (n + 1)
dp[0] = True # [关键] 空串可达
for j in range(1, n + 1): # 外层：前缀终点
for w in word_set: # 内层：字典单词
L = len(w)
if j >= L and dp[j - L] and s[j - L:j] == w:
dp[j] = True
break # [可选] 找到一种即可
return dp[n]
print(Solution().wordBreak("leetcode", ["leet", "code"])) # True
print(Solution().wordBreak("applepenapple", ["apple", "pen"])) # True
print(Solution().wordBreak("catsandog", ["cats", "dog", "sand", "and", "cat"])) # False
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
word_set = set(wordDict) # [可选] 转 set 加速查找
dp = [False] * (n + 1)
dp[0] = True # [关键] 空串可达
for j in range(1, n + 1): # 外层：前缀终点
for w in word_set: # 内层：字典单词
L = len(w)
if j >= L and dp[j - L] and s[j - L:j] == w:
dp[j] = True
break # [可选] 找到一种即可
return dp[n]
print(Solution().wordBreak("leetcode", ["leet", "code"])) # True
print(Solution().wordBreak("applepenapple", ["apple", "pen"])) # True
print(Solution().wordBreak("catsandog", ["cats", "dog", "sand", "and", "cat"])) # False
True True False
3.7 组合总和 IV · 377（完全 · 排列数 · 模板 C）¶
给你一组正整数 nums 和目标 target，求排列数（[1,2] 和 [2,1] 算两种）。
- 状态：
dp[j]= 凑出 j 的排列数 - 转移：
dp[j] += dp[j - num] - 边界：
dp[0] = 1 - 遍历：模板 C · 先容量、后物品
- 和 518 正好外内层交换。同一容量 dp[j] 会尝试"所有物品作为最后一步"，自然算出排列数
核心区别：
先物品后容量（组合数）：外层固定物品顺序，每个物品只能按这个固定顺序被考虑加入背包。这样 dp[j] 只会记录“使用物品的某种排列”中的一种（即按物品循环顺序自然形成的排列），因此重复的排列被视作同一个组合。
先容量后物品（排列数）：外层遍历容量，内层遍历所有物品。对于每个容量 j，dp[j] 会从所有可能的 dp[j-num] 累加，而 dp[j-num] 本身已经包含了不同顺序的方案。最终结果自动包含了所有顺序排列
先容量后物品的结果为7 ---> 排列数
In [199]:
Copied!
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [0] * (target + 1)
dp[0] = 1 # [关键] 排列空集 = 1 种
for j in range(1, target + 1): # [注意] 模板 C：先容量（顺序敏感）
for num in nums: # [注意] 后物品
if j >= num:
dp[j] += dp[j - num]
return dp[target]
print(Solution().combinationSum4([1, 2, 3], target=4)) # 7
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [0] * (target + 1)
dp[0] = 1 # [关键] 排列空集 = 1 种
for j in range(1, target + 1): # [注意] 模板 C：先容量（顺序敏感）
for num in nums: # [注意] 后物品
if j >= num:
dp[j] += dp[j - num]
return dp[target]
print(Solution().combinationSum4([1, 2, 3], target=4)) # 7
7
先物品后容量的结果为4 ---> 组合数
In [200]:
Copied!
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [0] * (target + 1)
dp[0] = 1 # [关键] 排列空集 = 1 种
for num in nums:
for j in range(num, target+1):
dp[j] += dp[j-num]
return dp[target]
print(Solution().combinationSum4([1, 2, 3], target=4)) # 4
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [0] * (target + 1)
dp[0] = 1 # [关键] 排列空集 = 1 种
for num in nums:
for j in range(num, target+1):
dp[j] += dp[j-num]
return dp[target]
print(Solution().combinationSum4([1, 2, 3], target=4)) # 4
4
第 4 章 · 双序列 DP（M4）¶
特征：问题涉及两个字符串或数组，答案来自二者的交互匹配。
统一命名：dp[i][j], m, n = len(s1), len(s2), 访问原串用 s1[i-1] / s2[j-1]（因 dp 多开一位）。
+1 决策：✅ 必须 +1。dp[0][j] 表示 "s1 空串 vs s2 前 j 个"，会被 dp[i-1][j-1] 在转移中真实引用，必须物理存在。
转移依赖模式：dp[i][j] 几乎总是依赖 dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1] 中的若干个。
遍历顺序：for i in range(1, m+1): for j in range(1, n+1):
4.1 最长公共子序列 · 1143¶
返回两个字符串的最长公共子序列长度（子序列不连续）。
- 状态：
dp[i][j]= s1[:i] 与 s2[:j] 的 LCS 长度 - 转移：
- 若
s1[i-1] == s2[j-1]：dp[i][j] = dp[i-1][j-1] + 1 - 否则：
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
- 若
- 边界：
dp[0][*] = dp[*][0] = 0
In [201]:
Copied!
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)]
# [冗余] dp[0][*] 和 dp[*][0] 默认即 0
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]
print(Solution().longestCommonSubsequence("abcde", "ace")) # 3
print(Solution().longestCommonSubsequence("abc", "def")) # 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)]
# [冗余] dp[0][*] 和 dp[*][0] 默认即 0
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]
print(Solution().longestCommonSubsequence("abcde", "ace")) # 3
print(Solution().longestCommonSubsequence("abc", "def")) # 0
3 0
In [202]:
Copied!
def longest_common_subsequence_str(s1: str, s2: str) -> str:
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
# 回溯
i, j = m, n
chars = []
while i > 0 and j > 0:
if s1[i - 1] == s2[j - 1]:
chars.append(s1[i - 1])
i -= 1
j -= 1
elif dp[i - 1][j] >= dp[i][j - 1]:
i -= 1
else:
j -= 1
return ''.join(reversed(chars))
print(longest_common_subsequence_str("abcde", "ace")) # ace
def longest_common_subsequence_str(s1: str, s2: str) -> str:
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
# 回溯
i, j = m, n
chars = []
while i > 0 and j > 0:
if s1[i - 1] == s2[j - 1]:
chars.append(s1[i - 1])
i -= 1
j -= 1
elif dp[i - 1][j] >= dp[i][j - 1]:
i -= 1
else:
j -= 1
return ''.join(reversed(chars))
print(longest_common_subsequence_str("abcde", "ace")) # ace
ace
4.2 编辑距离 · 72¶
s1 变成 s2 的最少操作数（操作：插入、删除、替换）。
- 状态：
dp[i][j]= s1[:i] 变成 s2[:j] 的最少操作数 - 转移：
- 若
s1[i-1] == s2[j-1]：dp[i][j] = dp[i-1][j-1]（无需操作） - 否则
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
- 若
- 边界（非默认值！）：
dp[0][j] = j（空串变长度 j 的串需 j 次插入）dp[i][0] = i（长度 i 的串变空串需 i 次删除）
In [203]:
Copied!
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 # [关键] 非零边界必写
for j in range(n + 1):
dp[0][j] = j # [关键] 非零边界必写
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]
print(Solution().minDistance("horse", "ros")) # 3
print(Solution().minDistance("intention", "execution")) # 5
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 # [关键] 非零边界必写
for j in range(n + 1):
dp[0][j] = j # [关键] 非零边界必写
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]
print(Solution().minDistance("horse", "ros")) # 3
print(Solution().minDistance("intention", "execution")) # 5
3 5
4.3 不同的子序列 · 115¶
给定字符串 s 和 t，返回 s 的子序列中等于 t 的个数（方案数）。
- 状态：
dp[i][j]= s[:i] 的子序列中等于 t[:j] 的方案数 - 转移（核心思考：s[i-1] 这个字符是否匹配 t[j-1]）：
- 若
s[i-1] == t[j-1]：既可以用也可以不用，dp[i][j] = dp[i-1][j-1] + dp[i-1][j] - 否则（必定不用）：
dp[i][j] = dp[i-1][j]
- 若
- 边界：
dp[i][0] = 1（t 是空串，s 任意前缀"删光"都能匹配）dp[0][j>0] = 0（s 空而 t 非空，无法匹配）
In [204]:
Copied!
class Solution:
def numDistinct(self, s: str, t: str) -> int:
m, n = len(s), len(t)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = 1 # [关键] t 空 → 方案数 1
for i in range(1, m + 1):
for j in range(1, n + 1):
if s[i - 1] == t[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
else:
dp[i][j] = dp[i - 1][j]
return dp[m][n]
print(Solution().numDistinct("rabbbit", "rabbit")) # 3
print(Solution().numDistinct("babgbag", "bag")) # 5
class Solution:
def numDistinct(self, s: str, t: str) -> int:
m, n = len(s), len(t)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = 1 # [关键] t 空 → 方案数 1
for i in range(1, m + 1):
for j in range(1, n + 1):
if s[i - 1] == t[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
else:
dp[i][j] = dp[i - 1][j]
return dp[m][n]
print(Solution().numDistinct("rabbbit", "rabbit")) # 3
print(Solution().numDistinct("babgbag", "bag")) # 5
3 5
4.4 两个字符串的删除操作 · 583¶
每步可删任一字符，求使 s1 和 s2 相同的最少操作数。
- 思路：类编辑距离但只允许"删除"
s1[i-1] == s2[j-1]：dp[i][j] = dp[i-1][j-1]- 否则：
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1
- 边界：
dp[0][j] = j, dp[i][0] = i
In [205]:
Copied!
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
for j in range(n + 1):
dp[0][j] = j
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]) + 1
return dp[m][n]
print(Solution().minDistance("sea", "eat")) # 2
print(Solution().minDistance("leetcode", "etco")) # 4
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
for j in range(n + 1):
dp[0][j] = j
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]) + 1
return dp[m][n]
print(Solution().minDistance("sea", "eat")) # 2
print(Solution().minDistance("leetcode", "etco")) # 4
2 4
4.5 最长重复子数组 · 718¶
返回两个数组连续公共子数组的最长长度。
- 注意"连续"：与 LCS（不连续）的差别仅在转移——不相等时 dp[i][j] = 0，而不是 max
- 状态：
dp[i][j]= 以nums1[i-1]和nums2[j-1]结尾的公共子数组长度 - 转移：
- 若
nums1[i-1] == nums2[j-1]：dp[i][j] = dp[i-1][j-1] + 1 - 否则：
dp[i][j] = 0
- 若
- 答案：
max(max(row) for row in dp)
In [206]:
Copied!
class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
m, n = len(nums1), len(nums2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
ans = 0
for i in range(1, m + 1):
for j in range(1, n + 1):
if nums1[i - 1] == nums2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
ans = max(ans, dp[i][j])
# [注意] 不等时 dp[i][j] = 0（连续性），默认即 0 可省略
return ans
print(Solution().findLength([1, 2, 3, 2, 1], [3, 2, 1, 4, 7])) # 3
class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
m, n = len(nums1), len(nums2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
ans = 0
for i in range(1, m + 1):
for j in range(1, n + 1):
if nums1[i - 1] == nums2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
ans = max(ans, dp[i][j])
# [注意] 不等时 dp[i][j] = 0（连续性），默认即 0 可省略
return ans
print(Solution().findLength([1, 2, 3, 2, 1], [3, 2, 1, 4, 7])) # 3
3
第 5 章 · 网格 DP（M5）¶
特征：在二维网格上从左上走到右下（或类似路径结构），每步方向受限。
统一命名：dp[i][j], m, n = len(grid), len(grid[0])。
+1 决策：❌ 不 +1。虚拟"第 -1 行"无物理意义，手动填第一行 dp[0][j] 和第一列 dp[i][0] 更清晰。
转移依赖模式：dp[i][j] = f(dp[i-1][j], dp[i][j-1])（只能下或右走）。
5.1 不同路径 · 62¶
m×n 网格从左上走到右下（只能下或右），求路径数。
- 转移：
dp[i][j] = dp[i-1][j] + dp[i][j-1] - 边界：
dp[0][j] = 1（第一行只能一直右走），dp[i][0] = 1（第一列只能一直下走）
In [207]:
Copied!
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[0] * n for _ in range(m)]
for i in range(m):
dp[i][0] = 1 # [关键] 第一列全 1
for j in range(n):
dp[0][j] = 1 # [关键] 第一行全 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]
print(Solution().uniquePaths(3, 7)) # 28
print(Solution().uniquePaths(3, 2)) # 3
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[0] * n for _ in range(m)]
for i in range(m):
dp[i][0] = 1 # [关键] 第一列全 1
for j in range(n):
dp[0][j] = 1 # [关键] 第一行全 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]
print(Solution().uniquePaths(3, 7)) # 28
print(Solution().uniquePaths(3, 2)) # 3
28 3
5.2 不同路径 II · 63（带障碍）¶
网格中有障碍（grid[i][j] == 1），障碍不可通过，求路径数。
- 关键差异：遇到障碍直接
dp[i][j] = 0 - 边界：第一行/列一旦遇到障碍，后续全部置 0
In [208]:
Copied!
class Solution:
def uniquePathsWithObstacles(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
if grid[0][0] == 1 or grid[m - 1][n - 1] == 1:
return 0 # [关键] 起终点有障碍直接 0
dp = [[0] * n for _ in range(m)]
dp[0][0] = 1
for j in range(1, n):
dp[0][j] = 0 if grid[0][j] == 1 else dp[0][j - 1] # [注意] 遇障后续全 0
for i in range(1, m):
dp[i][0] = 0 if grid[i][0] == 1 else dp[i - 1][0]
for i in range(1, m):
for j in range(1, n):
if grid[i][j] == 1:
dp[i][j] = 0
else:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m - 1][n - 1]
print(Solution().uniquePathsWithObstacles([[0,0,0],[0,1,0],[0,0,0]])) # 2
class Solution:
def uniquePathsWithObstacles(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
if grid[0][0] == 1 or grid[m - 1][n - 1] == 1:
return 0 # [关键] 起终点有障碍直接 0
dp = [[0] * n for _ in range(m)]
dp[0][0] = 1
for j in range(1, n):
dp[0][j] = 0 if grid[0][j] == 1 else dp[0][j - 1] # [注意] 遇障后续全 0
for i in range(1, m):
dp[i][0] = 0 if grid[i][0] == 1 else dp[i - 1][0]
for i in range(1, m):
for j in range(1, n):
if grid[i][j] == 1:
dp[i][j] = 0
else:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m - 1][n - 1]
print(Solution().uniquePathsWithObstacles([[0,0,0],[0,1,0],[0,0,0]])) # 2
2
5.3 最小路径和 · 64¶
网格中每格有代价，求从左上到右下路径的最小代价和。
- 转移：
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] - 边界：第一行/列只能单方向累加
In [209]:
Copied!
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]
print(Solution().minPathSum([[1,3,1],[1,5,1],[4,2,1]])) # 7
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]
print(Solution().minPathSum([[1,3,1],[1,5,1],[4,2,1]])) # 7
7
5.4 三角形最小路径和 · 120¶
三角形数组，每步可走到下一行的当前位置或下一位置，求最小路径和。
- 状态：
dp[i][j]= 走到 (i, j) 的最小路径和 - 转移：
- j = 0：只能从
dp[i-1][0]来 - j = i：只能从
dp[i-1][j-1]来 - 其他：
min(dp[i-1][j], dp[i-1][j-1])
- j = 0：只能从
- 答案：
min(dp[-1])
In [210]:
Copied!
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
m = len(triangle)
dp = [row[:] for row in triangle] # [可选] 复制一份避免原地修改
for i in range(1, m):
for j in range(i + 1):
if j == 0:
dp[i][j] = dp[i - 1][0] + triangle[i][j]
elif j == i:
dp[i][j] = dp[i - 1][j - 1] + triangle[i][j]
else:
dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j]
return min(dp[-1])
print(Solution().minimumTotal([[2],[3,4],[6,5,7],[4,1,8,3]])) # 11
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
m = len(triangle)
dp = [row[:] for row in triangle] # [可选] 复制一份避免原地修改
for i in range(1, m):
for j in range(i + 1):
if j == 0:
dp[i][j] = dp[i - 1][0] + triangle[i][j]
elif j == i:
dp[i][j] = dp[i - 1][j - 1] + triangle[i][j]
else:
dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j]
return min(dp[-1])
print(Solution().minimumTotal([[2],[3,4],[6,5,7],[4,1,8,3]])) # 11
11
5.5 最大正方形 · 221¶
0/1 矩阵中找最大的全 1 正方形的面积。
- 状态：
dp[i][j]= 以 (i, j) 为右下角的最大正方形边长 - 转移（只在
matrix[i][j] == '1'时有效）：dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
- 边界：第一行/列直接等于
matrix[i][j] - 答案：
max(dp) ** 2
In [211]:
Copied!
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
m, n = len(matrix), len(matrix[0])
dp = [[0] * n for _ in range(m)]
side = 0
for i in range(m):
for j in range(n):
if matrix[i][j] == '1':
if i == 0 or j == 0:
dp[i][j] = 1 # [关键] 第一行/列：自身即正方形
else:
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
side = max(side, dp[i][j])
return side * side
print(Solution().maximalSquare([["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]])) # 4
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
m, n = len(matrix), len(matrix[0])
dp = [[0] * n for _ in range(m)]
side = 0
for i in range(m):
for j in range(n):
if matrix[i][j] == '1':
if i == 0 or j == 0:
dp[i][j] = 1 # [关键] 第一行/列：自身即正方形
else:
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
side = max(side, dp[i][j])
return side * side
print(Solution().maximalSquare([["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]])) # 4
4
第 6 章 · 区间 DP（M6）¶
特征：状态是一段区间 [i, j]，答案依赖更小的子区间。
统一命名：dp[i][j]（i = 左端点，j = 右端点），外层循环区间长度，内层循环起点。
+1 决策：❌ 不 +1。i, j 直接是区间端点下标，无"空区间"语义。
边界：长度 1 的区间（i == j）和长度 2 的区间（j = i + 1）通常单独处理。
遍历顺序（关键）：必须按区间长度从小到大遍历，保证计算 dp[i][j] 时 dp[i+1][j-1] 已算好：
for length in range(2, n + 1): # 区间长度
for i in range(n - length + 1): # 起点
j = i + length - 1 # 终点
区间 DP 与双序列 DP 都用
dp[i][j]但含义完全不同：这里 i, j 是同一个序列的两端，双序列 DP 的 i, j 是两个序列的长度。
6.1 最长回文子串 · 5¶
返回 s 中最长回文子串。
- 状态：
dp[i][j]= s[i..j] 是否回文（bool） - 转移：
- 长度 1：
dp[i][i] = True - 长度 2：
dp[i][i+1] = (s[i] == s[i+1]) - 长度 ≥ 3：
dp[i][j] = dp[i+1][j-1] and s[i] == s[j]
- 长度 1：
- 记录答案：遍历时追踪最长回文的起点与长度
In [212]:
Copied!
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 # [关键] 长度 1 一定回文
for length in range(2, n + 1): # [注意] 必须按长度递增
for i in range(n - length + 1):
j = i + length - 1
if s[i] != s[j]:
dp[i][j] = False
elif length == 2:
dp[i][j] = True # [关键] 长度 2 单独判定
else:
dp[i][j] = dp[i + 1][j - 1]
if dp[i][j] and length > max_len:
start, max_len = i, length
return s[start:start + max_len]
print(Solution().longestPalindrome("babad")) # bab 或 aba
print(Solution().longestPalindrome("cbbd")) # bb
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 # [关键] 长度 1 一定回文
for length in range(2, n + 1): # [注意] 必须按长度递增
for i in range(n - length + 1):
j = i + length - 1
if s[i] != s[j]:
dp[i][j] = False
elif length == 2:
dp[i][j] = True # [关键] 长度 2 单独判定
else:
dp[i][j] = dp[i + 1][j - 1]
if dp[i][j] and length > max_len:
start, max_len = i, length
return s[start:start + max_len]
print(Solution().longestPalindrome("babad")) # bab 或 aba
print(Solution().longestPalindrome("cbbd")) # bb
bab bb
6.2 回文子串 · 647¶
给你一个字符串 s，返回回文子串的数目（不同位置即使内容相同也各自计数）。
- 状态：
dp[i][j]= s[i..j] 是否回文（复用 5 的定义） - 转移：完全同 5
- 答案：
dp[i][j] == True的 (i,j) 对数
In [213]:
Copied!
class Solution:
def countSubstrings(self, s: str) -> int:
n = len(s)
dp = [[False] * n for _ in range(n)]
count = 0
for i in range(n):
dp[i][i] = True
count += 1
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 or dp[i + 1][j - 1]:
dp[i][j] = True
count += 1
return count
print(Solution().countSubstrings("abc")) # 3
print(Solution().countSubstrings("aaa")) # 6
class Solution:
def countSubstrings(self, s: str) -> int:
n = len(s)
dp = [[False] * n for _ in range(n)]
count = 0
for i in range(n):
dp[i][i] = True
count += 1
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 or dp[i + 1][j - 1]:
dp[i][j] = True
count += 1
return count
print(Solution().countSubstrings("abc")) # 3
print(Solution().countSubstrings("aaa")) # 6
3 6
6.3 最长回文子序列 · 516 ⭐¶
返回 s 中最长回文子序列（可不连续）的长度。
- 状态：
dp[i][j]= s[i..j] 的最长回文子序列长度 - 转移：
- 若
s[i] == s[j]：dp[i][j] = dp[i + 1][j - 1] + 2 - 否则：
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
- 若
- 边界：
dp[i][i] = 1（单字符回文长度 1） - 答案：
dp[0][n - 1]
In [214]:
Copied!
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 1 # [关键] 单字符长度为 1
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
return dp[0][n - 1]
print(Solution().longestPalindromeSubseq("bbbab")) # 4 (bbbb)
print(Solution().longestPalindromeSubseq("cbbd")) # 2
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 1 # [关键] 单字符长度为 1
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
return dp[0][n - 1]
print(Solution().longestPalindromeSubseq("bbbab")) # 4 (bbbb)
print(Solution().longestPalindromeSubseq("cbbd")) # 2
4 2
附录 · 技术模块 × 题目对照表¶
遮住代码只看这张表，应该能复述每道题的状态定义、转移公式、边界处理。
| 题号 | 题目 | 模块 | 是否 +1 | 核心状态 |
|---|---|---|---|---|
| 70 | 爬楼梯 | M1 | ❌ | dp[i] = dp[i-1]+dp[i-2] |
| 746 | 最小花费爬楼梯 | M1 | ⚠ 被动 | dp[i] = min 两条来路（题目到 n 楼顶） |
| 198 | 打家劫舍 | M1 | ❌ | dp[i] = max(dp[i-1], dp[i-2]+v) |
| 213 | 打家劫舍 II | M1 | ❌ | 两次线性 DP 取最大 |
| 53 | 最大子数组 | M1 | ❌ | 以 i 结尾的最大和 |
| 118 | 杨辉三角 | M1 | ❌ | dp[i][j]=dp[i-1][j-1]+dp[i-1][j] |
| 300 | 最长递增子序列 | M1 | ❌ | 以 i 结尾的 LIS |
| 32 | 最长有效括号 | M1 | ❌ | 以 i 结尾的有效长度 |
| 152 | 乘积最大子数组 | M2 | ❌ | fmax / fmin 同步 |
| 121 | 股票 · 一次 | M2 | ❌ | dp[i][0/1]，买入用 -price |
| 122 | 股票 · 多次 | M2 | ❌ | 买入用 dp[i-1][0]-price |
| 309 | 股票 · 冷冻期 | M2 | ❌ | 买入用 dp[i-2][0] |
| 714 | 股票 · 手续费 | M2 | ❌ | 卖出减 fee |
| 416 | 分割等和子集 | M3 | ✅ | 0/1 · 是否可达 |
| 494 | 目标和 | M3 | ✅ | 0/1 · 方案数 |
| 322 | 零钱兑换 | M3 | ✅ | 完全 · 最少物品 |
| 518 | 零钱兑换 II | M3 | ✅ | 完全 · 组合数 |
| 279 | 完全平方数 | M3 | ✅ | 完全 · 最少物品 |
| 139 | 单词拆分 | M3 | ✅ | 完全 · 是否可达（一维） |
| 377 | 组合总和 IV | M3 | ✅ | 完全 · 排列数（先容量后物品） |
| 1143 | 最长公共子序列 | M4 | ✅ | 匹配相等 vs 两侧 max |
| 72 | 编辑距离 | M4 | ✅ | 三向 min + 1 |
| 115 | 不同的子序列 | M4 | ✅ | 匹配时相加 |
| 583 | 两字符串删除 | M4 | ✅ | 类编辑距离，只删除 |
| 718 | 最长重复子数组 | M4 | ✅ | 不匹配时 dp=0（连续性） |
| 62 | 不同路径 | M5 | ❌ | 下+右路径数 |
| 63 | 不同路径 II | M5 | ❌ | 障碍置 0 |
| 64 | 最小路径和 | M5 | ❌ | 下+右 min |
| 120 | 三角形 | M5 | ❌ | 边界位置特判 |
| 221 | 最大正方形 | M5 | ❌ | 三向 min + 1 |
| 5 | 最长回文子串 | M6 | ❌ | 长度递增递推 |
| 647 | 回文子串 | M6 | ❌ | 同 5 · 计数 |
| 516 | 最长回文子序列 | M6 | ❌ | 相等+2 / 不等两侧 max |
+1 决策的图例：
- ❌ 不 +1：6 个模块中的 M1、M2、M5、M6
- ✅ 必须 +1：M3 背包、M4 双序列
- ⚠ 被动 +1：题目定义要求（如 746 的楼顶位置），不是主动选择
五类注释标签速查¶
| 标签 | 含义 | 典型场景 |
|---|---|---|
[关键] |
核心边界/转移，删掉就错 | 非默认的初始化值、转移公式 |
[冗余] |
Python 默认已满足，写出仅为强调语义 | dp[0] = 0 when already 0 |
[哨兵] |
极值初始化（inf / -inf） | 求最小值的 DP |
[可选] |
性能/实现优化，不影响正确性 | 剪枝 / break / 用 set 加速 |
[注意] |
易错点或语义的一部分 | 遍历顺序、索引偏移 |
边界判断三层法速查¶
- 转移是否越界？（
dp[i-1]→ i=0 必须边界） - dp[0] 是否被转移引用参与计算？（✅ 必须 +1；❌ 不 +1）
- 边界值是否等于默认？（等于 → 冗余可省；不等于 → 必写）