📑 本页目录（点开跳转）
05 · 动态规划：把今天交给昨天
⏱ 8 分钟 ｜ 最大子数组、跳台阶、正则匹配
🎯 一句话
动态规划不是公式收集：先定义一句“dp[i] 到底代表什么”，再只从已经解决的小问题推当前问题。
🧩 题 1：连续子数组的最大和
走到当前数字时，只有两个选择：接着前一段，或者从我自己重新开始。
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。
🧩 题 2：跳台阶
到第 n 阶，最后一步不是从 n-1 来，就是从 n-2 来。因此答案等于两种走法相加。
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
🧩 题 3：正则表达式匹配（. 和 *）
这题难在 *：它可以让前一个字符出现 0 次，也可以吃一个字符后继续留在原模式。
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
⭐ 看见“很多子问题重复算”，先考虑记忆化；它就是从递归过渡到动态规划的桥。
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| 强化学习基础 04 · 动态规划 | ⚠️ 同名不同物，但同一个思想：那里的「动态规划」指的是环境规则已知时直接迭代解贝尔曼方程。⭐ 两边共用的那句话是「今天的最优由昨天的状态推出来」 |
🛑 可以停在这里
DP 的第一行不是代码，是中文：“我的状态代表什么？”
✅ 检查点
最大子数组题为什么不能只记录全局最大和？
👀 看答案
下一轮需要知道“以当前点结尾”的最佳前缀能否接上。全局最大和可能结束在很早的位置，不能直接接。
⚡ 走神救援
- DP 先用一句话定义状态。
- 最大子数组：接前一段，或从自己重开。
*有两条路：跳过“字符+星号”，或吃一个字符后继续匹配。