🏠 总目录📚 本教程 05 · 动态规划:把今天交给昨天 ← →
📑 本页目录(点开跳转)

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 取两个数中较大的一个。

逐项手算 [5, -8, 2, 4]
下标与净收入只选当天 / 接上前段当前结尾 / 扫到目前
0,5初始化为 55 / 5
1,−8−8 / 5 − 8 = −3−3 / 5
2,22 / −3 + 2 = −12 / 5
3,44 / 2 + 4 = 66 / 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 阶向上填表
目标阶到达它的方法数
01(不走)
11(跳 1 阶)
2f(1) + f(0) = 1 + 1 = 2
3f(2) + f(1) = 2 + 1 = 3
4f(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)。 向右走一步添一个左括号,向上走一步添一个右括号。每条路的走法唯一确定括号顺序,反过来读一个合法串也唯一确定一条路。

三对括号的合法路径和首次越界 1 × × × 1 1 × × 1 2 2 × 1 3 5 5 0 0 1 1 2 2 3 3 右括号 R 左括号 L 禁区
三对括号的 4×4 状态图。圆内是走法数;箭头向右添左括号、向上添右括号。虚箭和 × 标出 ())(() 首次越界。

图的文字读法:从左下角 (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 次,文本不动,模式跳两格。让它匹配一次,要先确认当前字符匹配,然后只挪文本下标。模式留在原地,下一步还可以再匹配一次,也可以跳过。只要一条路成功,当前状态就为真。

手算 bbq 能否完整匹配 a*b*q
状态下一步
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。


⚡ 走神救援

继续: 06 · 回溯与矩阵:试完一条路怎么干净回来

打卡记录保存在你的浏览器里,首页能看到总进度