学习顺序主线第 22 / 22 课 · 阶段 7

为什么现在学:最后把数组、递归和复杂度串起来,学习对重复子问题做缓存。

返回算法课程
动态规划基础

动态规划入门Dynamic Programming

把重复出现的子问题只计算一次,再用已知答案构造更大的答案。

50 分钟前置:数组 · 循环 · 递归基础

学完这一课,你应该能做到

  • 用一句话精确定义状态
  • 证明按最后一步分类无重无漏
  • 从递归树到表格,再到滚动变量

01先从一个问题出发

每次能走 1 级或 2 级台阶,到达第 n 级有几种不同走法?

一个具体的例子

n=4,dp[i] 计数恰好到第 i 级的走法。

先列小答案,再寻找分类方式

一次走 1 或 2 级台阶,走法中的顺序不同算不同方案。n=3 时有 1+1+1、1+2、2+1 三种。我们问的是方案数,不是最少步数,也不是列出所有方案。

考虑任意到达第 n 级的走法,最后一步只能走 1 或 2。前一种走法来自 n−1 级的任意合法走法,后一种来自 n−2 级。两类最后一步不同,不会重复;又覆盖所有可能,所以可以把方案数相加。

递归树里,重复的是同一个问题

直接递归 ways(4)=ways(3)+ways(2),而 ways(3) 又调用 ways(2)+ways(1)。两个 ways(2) 的输入与问题完全相同,没有必要算两遍。注意这是『相同状态』,不是两个结果碰巧相等。

定义 dp[i] 为恰好到达第 i 级的方法数。以递增 i 填表,每次所需的 dp[i−1]、dp[i−2] 已算好。dp[0]=1 表示唯一的空走法;否则到达第 2 级的『直接走两级』会找不到一个合法起点贡献。

先写清模型,再压缩空间

一个 DP 至少应回答五件事:状态是什么、转移为什么成立、初值是什么、以什么顺序计算、最终读哪一项。先用表格把这些关系做对,再观察只依赖最近两项,决定用两个变量代替整张表。

不能见到最优值或计数就机械套这个递推。若每次可走 1 或 3 级,依赖变成 i−1 和 i−3;若有不能踩的台阶,对应状态要为 0;若问最少步数,合并候选应使用 min 并加一步。模型决定公式。

02最直接的办法,为什么慢?

递归尝试最后一步走 1 级或 2 级。

暴力 · O(2ⁿ) 上界

ways(n−2) 等子问题会出现在多个分支中,被重复求解。

03一步步,推导出优化思路

1

先定义每个状态的含义

定义状态:dp[i] 是恰好走到第 i 级的方法数。

2

按最后一步分类,得到转移

按最后一步分类,两类互斥且覆盖全部走法:dp[i]=dp[i−1]+dp[i−2]。

3

从空路径开始,按依赖顺序填表

设置 dp[0]=1,按台阶数递增计算,确保依赖已经就绪。

贯穿算法的不变量

计算 dp[i] 时,所有更小下标的状态已经正确计算。

拿一个小输入,逐步手算

n=4,dp[i] 计数恰好到第 i 级的走法。

i最后一步为 1 的贡献最后一步为 2 的贡献dp[i]
0空走法—1
1dp[0]=1不存在1
2dp[1]=1dp[0]=12
3dp[2]=2dp[1]=13
4dp[3]=3dp[2]=25

5 种走法为 1111、112、121、211、22。112、121、211 的步长数量一样,但顺序不同,在本题模型中是不同方案。

无重无漏的分类,比背公式更重要

  1. 基础状态 dp[0]=1 表示空路径,dp[1]=1 表示唯一的一步。
  2. 把到达 i 的走法按最后一步大小分成互斥的两类。删除最后一步分别与到 i−1、i−2 的走法一一对应,因此相加正确。
  3. 按 i 递增填表,所有依赖都已经正确计算。由归纳可知 dp[n] 就是题目所求,而不是整张表的和。

04让每一步,都看得见

试着先预测下一步,再点击「下一步」验证。变量、动画与代码会同步变化。

Dynamic Programming交互演示
STEP 01 / 10
0
0
0
1
0
2
0
3
0
4

dp[i] = dp[i − 1] + dp[i − 2] · 橙色格正在计算

当前处理已处理 / 已确定未处理
01

dp[i] 表示到达第 i 级台阶的方法数,先全部初始化为 0。

dynamic_programming.py参考实现 · 当前第 2 行
正在载入代码编辑器…

动画展示参考实现的执行轨迹。切换语言时,当前操作会定位到对应代码行。

代码里的每个关键决定

dp = [0] * (n + 1)
包括状态 0 到 n,一共 n+1 个状态。分配 n 项会在写 dp[n] 时越界。
dp[0] = 1
这是计数模型的单位起点,不是『有一级楼梯』。本课明确允许 n=0,返回唯一空走法的数量 1。
dp[step] = dp[step - 1]
先计入最后走 1 级的方案。step=1 时已经足够,不应读负下标 dp[−1]。
if step >= 2:
只在最后一步可以合法走 2 级时,加入 dp[step−2]。条件体现了可达范围。

05复杂度,来自具体的工作量

时间复杂度
O(n)O(n)

只有 n+1 个不同状态,每个状态最多做一次加法,因此 O(n)。这里按定长整数运算计数;任意精度整数的位成本需要另算。

辅助空间
O(n)O(n)

表格保存 n+1 个状态。由于只依赖前两项,可进一步用两个变量压缩为 O(1) 辅助空间。

拖动 n,看看增长速度

把工作量具体数出来

朴素递归的调用树分叉,时间可用 O(2^n) 作为上界;记忆化和表格法只求解 n+1 个不同状态,每个做常数次转移,按定长加法计 O(n)。

表格保存 n+1 项,空间 O(n)。若只需最终数量,可保留前两项,辅助空间 O(1);若要回看表格或重建方案,可能仍需更多记录。

结果数值很快增大。Python 大整数的加法不是永远常数成本;C++ 和 JavaScript 还各有数值范围限制。本页实验 n≤20,避免把溢出误认成算法问题。

06看到什么,应该想到它?

关键词只是线索,继续检查适用条件

07这些细节,容易踩坑

01

状态含义先说清

dp[i] 是方案数,不是最少步数;不同目标对应不同转移。

02

初始化也是模型一部分

dp[0]=1 表示唯一的空路径,否则无法统一计算最初状态。

03

先证明分类无重无漏

相加时两类走法必须互斥;状态不能遗漏影响未来的信息。

用反例检查前提

把 dp[0] 设成 0 会丢掉合法方案

若 dp[0]=0 且按本课代码逐项计算,dp[1]=0,dp[2]=0,所有项都会成为 0。甚至手设 dp[1]=1,也会漏算从起点直接跨两级的方案。

怎样修正:把每个初值翻译成题意,而不是照抄常见的 0 或 1;计数中的空选择有时贡献 1,最小代价问题中的起点则常贡献 0。

08把想法带进真实题目

合上答案,自己推一次

改变题目,自己改转移

现在每次可以走 1 或 3 级。定义同样的 dp[i],求 dp[0] 到 dp[4],并列出到第 4 级的全部走法。

需要一点提示

最后一步改成 3,只有 i≥3 时才加入 dp[i−3]。

查看完整推导与答案
  1. dp[0]=1;dp[1]=1,dp[2]=1。
  2. dp[3]=dp[2]+dp[0]=2;dp[4]=dp[3]+dp[1]=3。
  3. 到第 4 级的走法为 1111、13、31。不是把旧公式背得更熟,而是从新的最后一步重新分类。

完成上面的手算练习,再把思路迁移到这些题目。

09不用背模板,回答这几个问题

01dp[0] 为什么等于 1?

02时间从指数降为线性的原因?

03能否只保存最近两项?

你已经走完了这次推导。

能用自己的话解释复杂度和不变量,再标记为掌握。

把知识连起来

继续阅读

本课例子与推导为本站编写。需要另一种表述或进一步学习时,可对照这些公开课程与文档:

MIT 6.006 · 算法讲义Princeton Algorithms · 课程资料

能独立完成本课练习,再标记掌握。也可以直接用上面的链接继续学习。