📑 本页目录(点开跳转)
05 · 动态规划:把今天交给昨天
⏱ 8 分钟 | 最大子数组、跳台阶、正则匹配
🎯 一句话
动态规划不是公式收集:先定义一句“dp[i] 到底代表什么”,再只从已经解决的小问题推当前问题。
如果你刚学完上一章,可以沿用“先数实际做了几次操作”的方法。本章练习一件新事:遇到同一个小问题时,把答案留下来。读完后,试着独立写出状态、起点、转移、顺序、答案这五项。
🧩 题 1:连续子数组的最大和
走到当前数字时,只有两个选择:接着前一段,或者从我自己重新开始。
只记最大和,为什么接不上下一段?
设每天的净收入依次为 [5, -8, 2, 4],选至少一天且必须连续。读到第三天时,前两天的最高总和是第一天的 5。直接加上第三天的 2 会得到 7,却跳过了第二天的亏损。
动态规划(Dynamic Programming,DP)把大问题拆成定义明确的小问题,并复用它们的答案。这里需要保存的是必须结束在当前下标的最佳区间。下一步接上它时,区间依旧连续。
令 a[i] 是从 0 开始编号的第 i 项,E[i] 是必须以该项结尾的最大连续和,A[i] 是扫描到该项为止的全局最大连续和。只有第一项时,两者都等于 a[0]。
从第二项开始,区间要么只含当前项,要么是某段以 i−1 结尾的区间加上当前项。所有可接的区间加上同一个数,原先最大的仍然最大,所以只需要上一步的 E[i−1]。取两种选择中的较大值 E[i] = max(a[i], E[i−1] + a[i])。再和此前的全局最大值比较,得到 A[i] = max(A[i−1], E[i])。这里 max 取两个数中较大的一个。
| 下标与净收入 | 只选当天 / 接上前段 | 当前结尾 / 扫到目前 |
|---|---|---|
| 0,5 | 初始化为 5 | 5 / 5 |
| 1,−8 | −8 / 5 − 8 = −3 | −3 / 5 |
| 2,2 | 2 / −3 + 2 = −1 | 2 / 5 |
| 3,4 | 4 / 2 + 4 = 6 | 6 / 6 |
最后读 A[3] 得到 6,来自最后两天。下一段 Python 用 best_ending_here 保存最新的 E,用 best_so_far 保存最新的 A,不用整张表。每轮先更新结尾,再更新全局。
def max_subarray(nums):
best_ending_here = best_so_far = nums[0]
for value in nums[1:]:
best_ending_here = max(value, best_ending_here + value)
best_so_far = max(best_so_far, best_ending_here)
return best_so_far
assert max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6
状态:best_ending_here 是“必须以当前位置结尾”的最大和;它不等于全局答案,所以还要 best_so_far。
非空区间:[-4, -2] 的最大和是 −2。 非空整数列表至少选一项,所以单元素直接返回自身。把全局最大值初设为 0 会误选空区间。空列表会在 nums[0] 处报错。
切片 nums[1:] 额外占 O(n) 空间。 按基本算术为常数时间估计,扫描 n 个数花 O(n) 时间。两个状态变量只占常量空间,按下标遍历原列表才可省去复制,实现 O(1) 额外空间。
🧩 题 2:跳台阶
到第 n 阶,最后一步不是从 n-1 来,就是从 n-2 来。因此答案等于两种走法相加。
同一格可以被问多次,答案只算一次
约定从第 0 阶出发,每步跳 1 阶或 2 阶,且落在目标阶上。令 f(k) 表示恰好到第 k 阶的走法数。第 4 阶需要第 3 阶和第 2 阶的答案,而第 3 阶也需要第 2 阶。逐条展开递归会重复询问第 2 阶,沿下表填一遍就能复用。
对 k ≥ 2,最后跳 1 阶或 2 阶的走法互不重叠,也覆盖所有走法,因此 f(k) = f(k−1) + f(k−2)。第 0 阶已经到达,空走法有 1 种。第 1 阶只有走一步这 1 种。
| 目标阶 | 到达它的方法数 |
|---|---|
| 0 | 1(不走) |
| 1 | 1(跳 1 阶) |
| 2 | f(1) + f(0) = 1 + 1 = 2 |
| 3 | f(2) + f(1) = 2 + 1 = 3 |
| 4 | f(3) + f(2) = 3 + 2 = 5 |
把表压成两个变量叫滚动状态。算第 4 阶前,previous = 2、current = 3。Python 同时赋值先算右边,再把这对数更新为 (3, 5)。若先覆盖 previous 再直接用它做加法,就会错算成 3 + 3。
def jump_ways(n):
if n < 0:
return 0
previous, current = 1, 1 # f(0), f(1)
for _ in range(2, n + 1):
previous, current = current, previous + current
return current
assert jump_ways(0) == 1
assert jump_ways(4) == 5
代码从第 2 阶起填表。目标为 0 或 1 时跳过循环,直接返回 1;目标为负整数时按不可达返回 0。按一次整数加法为一步计,共做 O(n) 次操作,保存常数个整数。精确计数很大时,Python 大整数所占的字节数和加法成本也会增长。
🔎 可选深入:从“两个前驱相加”到“三角形两个孩子取最小”
跳台阶把两个前驱的方案数相加;换成路径代价,就从两个可选孩子中取更小的一个。本小例明确约定:从顶到底,每步只走到下一行相同下标或右邻下标。来源题面只给出“三角形中最小路径之和”标题,这个约定不能冒充原题已经列出的全部条件。
dp[i] 表示“从正在保存的那一行第 i 项出发,到底部的最小代价”。末行已无后续选择,直接用它初始化;上移一行时更新为 row[i] + min(dp[i], dp[i+1])。
| 当前处理 | 有效 dp 前缀 | 为什么 |
|---|---|---|
| 末行 [4, 1, 6] | [4, 1, 6] | 最后一层的代价就是自身 |
| 上一行 [5, 3] | [6, 4] | 5+min(4,1);3+min(1,6) |
| 顶行 [2] | [6] | 2+min(6,4),得到最短路径和 |
# Python 3.13/3.14;本小例约定空输入返回 0
def triangle_min_sum(triangle):
if not triangle:
return 0
if any(len(row) != i + 1 for i, row in enumerate(triangle)):
raise ValueError("triangle row lengths must be 1, 2, 3, ...")
dp = list(triangle[-1]) # 复制末行,不改输入
for row in reversed(triangle[:-1]):
for i, value in enumerate(row): # 从左到右更新
dp[i] = value + min(dp[i], dp[i + 1])
return dp[0]
assert triangle_min_sum([[2], [5, 3], [4, 1, 6]]) == 6
assert triangle_min_sum([[0], [0, 10], [100, 1, 100]]) == 1
assert triangle_min_sum([[-3]]) == -3
assert triangle_min_sum([]) == 0⭐ 每行必须从左到右更新:计算 i 时,所需旧的 dp[i]、dp[i+1] 还没有被覆盖;已经更新的左邻不再读取。反向更新会把上一层新值错当下一层旧值,第二条断言正用于暴露这种错误。允许负数,所以不能靠“每层挑最小的数字”的贪心替代相邻路径约束。
n 行共有 O(n²) 项,时间 O(n²)、额外空间 O(n);这里的空输入与畸形行处理是本函数的 API 约定。输入不修改。相邻孩子的标准问题定义可对照 LeetCode 120 官方题面,不据此补写来源题库未给出的条件。
即使所有代价都是正数,逐行贪心也可能失败。把三行换成 [[2], [3, 4], [9, 8, 1]],第二行先选较便宜的 3,接下来只能选 9 或 8,最低是 2 + 3 + 8 = 13。先付 4 就能接到 1,总价是 2 + 4 + 1 = 7。
括号路径:只累加合法前缀
给定非负整数 n,数恰好含 n 个左括号和 n 个右括号的合法串。读到一半的那段开头叫前缀。每放一个右括号,都要有一个已出现、还没配对的左括号供它配对。比如 ())(() 虽然左右各 3 个,读到第 3 个字符时就有 1 个左括号、2 个右括号,已经配不上。
用 L、R 分别记已放入的左、右括号数,余额是 L−R。两者是字符个数。合法区域满足 0≤R≤L≤n;终点是 (n,n)。 向右走一步添一个左括号,向上走一步添一个右括号。每条路的走法唯一确定括号顺序,反过来读一个合法串也唯一确定一条路。
())(() 首次越界。图的文字读法:从左下角 (0,0) 出发,沿右箭头增加 L,沿上箭头增加 R。每格只从左邻和下邻接步。虚箭 (1,1)→(1,2) 越过 L=R,目的格余额为 −1;(2,3) 同在禁区。到右边 (3,2) 的下邻和左邻分别有 3、2 种,到终点 (3,3) 只剩下方的 5 种。
借用跳台阶的思路,把走到同一格的路径按最后一步分组。最后添左括号的来自 (L−1,R),最后添右括号的来自 (L,R−1)。两组互斥且覆盖全部合法路,所以把前驱的走法数相加。记 ways[L][R] 为到该格的合法路数。
$\mathrm{ways}[L][R]=\mathrm{ways}[L-1][R]+\mathrm{ways}[L][R-1].$
起点的空走法计 1,越界计 0。先按 L 递增,同列按 R 递增。 公式只用在起点以外的合法格。这样的顺序先算左边一列,再算当前列较低的格;越界包括负下标或 R>L。终点的数字就是答案。
三对时,分别代入图上的两个前驱:ways[3][2] = ways[2][2] + ways[3][1] = 2 + 3 = 5。再走到终点时,左邻 (2,3) 越界,三对得到 ways[3][3] = 0 + 5 = 5。零对时,终点就是起点,只有空串。
依据:MIT 6.042 习题 7 第 5 题,第 6–7 页。
用 Python 验证格子递推
函数输入 n,返回合法串数。先留好一张零表并写入空走法,再用两层循环访问合法格。from_open 取左邻,from_close 取下邻;缺邻或禁区贡献为零。若让循环访问禁区,非法前缀也会被传播。
def count_parentheses(n):
if n < 0:
raise ValueError("n must be nonnegative")
ways = [[0] * (n + 1) for _ in range(n + 1)]
ways[0][0] = 1
for left in range(n + 1):
for right in range(left + 1):
if left == right == 0:
continue
from_open = ways[left - 1][right] if left else 0
from_close = ways[left][right - 1] if right else 0
ways[left][right] = from_open + from_close
return ways[n][n]
for pairs in (0, 3, 4):
print(pairs, count_parentheses(pairs))输出三行,依次是 0 对得 1,3 对得 5,4 对得 14。这些是卡特兰数(Catalan numbers)。可对照 NIST DLMF 表 26.5.1。如果删掉前缀限制,让两层循环都走完整方格,三对会误算成 20。
🧩 题 3:正则表达式匹配(. 和 *)
* 有两路:跳过这一组,或在当前字符匹配时吃掉它并留在这一组。 跳过相当于让前一个字符出现零次。
用两个位置描述还没匹配的部分
本例只处理普通字符、匹配任意单个字符的 .,以及让前一个字符或点重复零次或多次的 *。输入模式须符合这个语法,例如开头不能单独出现星号。目标是匹配整段文本。
令 F(i, j) 表示从文本下标 i、模式下标 j 开始,剩余两段能否完全匹配。两个下标都从 0 开始。模式到末尾时,只有文本也到末尾才返回真。普通字符或点匹配一次时,两个下标都往前挪一格。
遇到字符加星号时有两条路。让它出现 0 次,文本不动,模式跳两格。让它匹配一次,要先确认当前字符匹配,然后只挪文本下标。模式留在原地,下一步还可以再匹配一次,也可以跳过。只要一条路成功,当前状态就为真。
| 状态 | 下一步 |
|---|---|
F(0, 0) | 首字符 b 和 a 不同,只能跳过 a*,到 F(0, 2)。 |
F(0, 2) | 试跳过 b* 时,F(0, 4) 的 b 和 q 不匹配。改为消耗一个 b,去 F(1, 2)。 |
F(1, 2) | F(1, 4) 仍然把 b 对上 q,失败。再消耗一个 b,去 F(2, 2)。 |
F(2, 2) | 跳过 b*,F(2, 4) 用 q 匹配 q,去 F(3, 5)。 |
F(3, 5) | 文本、模式都到末尾,返回真。 |
在代码里,match(i, j) 就是 F(i, j)。first 先检查文本还有字符,再判断能否匹配当前位置。or 按顺序试两条路,第一条成功就直接返回。空文本可以匹配 a*,因为能跳过它,但不能匹配单独的 a。
from functools import lru_cache
def regex_match(text, pattern):
@lru_cache(maxsize=None)
def match(i, j):
if j == len(pattern):
return i == len(text)
first = i < len(text) and pattern[j] in {text[i], '.'}
if j + 1 < len(pattern) and pattern[j + 1] == '*':
return match(i, j + 2) or (first and match(i + 1, j))
return first and match(i + 1, j + 1)
return match(0, 0)
assert regex_match('aaa', 'a*a') is True
assert regex_match('ab', '.*') is True
assert regex_match('ab', 'a') is False
记忆化(Memoization)是在第一次求出一个状态时把结果记下来,下次遇到同一状态直接读取。比如匹配 aa 和 a*a*b 时,可以先在第一个 a* 吃一个 a 再跳过,也可以先跳过再在第二个 a* 吃一个 a,两路都到 F(1, 2)。这段代码的 lru_cache 保存每对下标的真假结果。一次匹配中输入固定,因此相同下标总是对应相同的剩余问题。
若文本长 m、模式长 n,含末尾位置各有 m+1、n+1 个下标。按一次缓存查询平均 O(1) 计,时间和缓存空间的上界都是 O((m+1)(n+1))。每次调用至少推进一个下标,递归栈最多 O(m+n+1) 层。很长的输入仍可能超出 Python 的递归深度限制。
⭐ 看见“很多子问题重复算”,先考虑记忆化;它就是从递归过渡到动态规划的桥。
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| 强化学习基础 04 · 动态规划 | ⚠️ 同名不同物,但同一个思想:那里的「动态规划」指的是环境规则已知时直接迭代解贝尔曼方程。⭐ 两边共用的那句话是「今天的最优由昨天的状态推出来」 |
同样是合并子问题,问法决定动作。跳台阶用加法数走法,最大和与最小代价用比较找最优值,正则匹配用“或”判断可行性。如果任务还要求还原哪条路径最优,例如隐马尔可夫模型里的维特比解码,通常还要记下每个最优状态来自哪个前驱,仅保存分数无法直接沿路径回走。
下一章的矩阵路径多了一个条件:当前路径已经用过哪些格子。同一位置在两条路径上可能有不同的可选下一步,仅凭位置缓存结果就可能把两个不同问题混在一起。
本节回顾
DP 的第一行不是代码,是中文:“我的状态代表什么?”
✅ 检查点
最大子数组题为什么不能只记录全局最大和?
👀 看答案
下一轮需要知道“以当前点结尾”的最佳前缀能否接上。全局最大和可能结束在很早的位置,不能直接接。
试算 f(3)。如果误把 f(0) 设成 0,而 f(1) 仍是 1,你会少算哪一种走法?
👀 看答案
错误的表先得到 f(2) = 1 + 0 = 1,再得到 f(3) = 1 + 1 = 2。少算的是先跳 2 阶、再跳 1 阶。那条路从第 0 阶的空走法接出第一跳。
括号扩到四对时,从三对图右边界接一列,求终点 (4,4)。为什么只看左右括号的总数还会数进非法串?
看答案:四对括号怎么数
从底部往上加左邻和下邻。新列从 (4,0) 到 (4,4) 依次是 1+0=1、3+1=4、5+4=9、5+9=14、0+14=14。四对共 14 种。只看总数会把 ())(()() 算进去:虽然最终左右各 4 个,前 3 个字符已经让余额变成 −1。
匹配 bbq 和 b*q 时,如果 b* 一吃掉一个 b 就把模式移到 q,会发生什么?
👀 看答案
第二个 b 会直接跟 q 比较,匹配失败。正确做法是让模式继续指向 b*,先消耗第二个 b,再跳过 b* 去匹配 q。
⚡ 走神救援
- DP 先用一句话定义状态。
- 最大子数组:接前一段,或从自己重开。
*有两条路:跳过“字符+星号”,或吃一个字符后继续匹配。