数据结构与算法 / 系统课时
用线性状态解决爬楼梯问题
用线性状态解决爬楼梯问题
爬楼梯是最适合练习一维动态规划建模的例子:每个位置只依赖前两个位置。这里从状态定义开始,推导初始条件和转移方程,再把整张表压缩成两个变量。
学习目标
- 为线性序列问题定义含义明确的一维状态
- 从最后一步推导初始条件和状态转移方程
- 根据有限依赖范围把 空间压缩为
从最后一步定义状态
问题设定为:有 n 级台阶,每次只能上 1 级或 2 级,求到达第 n 级共有多少种走法。
定义 dp[i] 为恰好到达第 i 级台阶的走法数量。到达第 i 级之前,最后一步只有两种可能:从第 i-1 级走 1 级,或者从第 i-2 级走 2 级。因此两类方案互不重叠,可以直接相加:
这里的建模关键是从“最后一步来自哪里”反推依赖。只要一个线性位置只依赖前面固定数量的位置,就很可能形成类似的一维 DP。
确定初始条件
令 dp[0]=1,表示站在起点、不走任何一步也算一种到达起点的方式;令 dp[1]=1,因为到第一级只有一种走法。这样从 i=2 开始,统一使用同一个转移式,不需要为第二级额外写特殊分支。
前几个状态因此依次为:
| i | dp[i] |
来源 |
|---|---|---|
| 0 | 1 | 空路径 |
| 1 | 1 | 从起点走 1 级 |
| 2 | 2 | dp[1] + dp[0] |
| 3 | 3 | dp[2] + dp[1] |
| 4 | 5 | dp[3] + dp[2] |
| 5 | 8 | dp[4] + dp[3] |
用递推表实现
下面同时保留完整 DP 表和空间压缩版本,便于检查两种实现是否得到相同答案。
def climb_table(n: int) -> tuple[int, list[int]]:
if n < 0:
raise ValueError('n must be non-negative')
dp = [0] * (n + 1)
dp[0] = 1
if n >= 1:
dp[1] = 1
# 当前状态只依赖前两个已经计算好的状态。
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n], dp
def climb_compressed(n: int) -> int:
if n < 0:
raise ValueError('n must be non-negative')
if n <= 1:
return 1
prev2, prev1 = 1, 1
# 只保留下一次转移仍会使用的两个状态。
for _ in range(2, n + 1):
prev2, prev1 = prev1, prev2 + prev1
return prev1
ways, states = climb_table(5)
print(states)
print(ways)
print(climb_compressed(5))预期输出
[1, 1, 2, 3, 5, 8]
8
8完整递推表需要保存 n+1 个状态,因此时间复杂度为 、空间复杂度为 。每个状态只计算一次,所以不会出现朴素递归中重复展开相同子问题的指数级开销。
压缩不再需要的状态
计算 dp[i] 时只读取 dp[i-1] 和 dp[i-2],更早的状态之后不会再参与计算。因此无需保存整张表,只要用 prev1 和 prev2 维护最近两个值即可。
更新两个变量时要注意赋值顺序。Python 的并行赋值会先计算右侧,再统一写回,因此 prev2, prev1 = prev1, prev2 + prev1 不会丢失旧值。在不支持并行赋值的语言中,应使用临时变量保存新状态。
空间压缩后,时间复杂度仍是 ,额外空间降为 。这种优化成立的前提不是“DP 表一定能删掉”,而是未来状态只依赖一个固定大小的历史窗口;如果后续转移还需要更早的数据,就必须继续保留那些状态。