数据结构与算法 / 系统课时

用线性状态解决爬楼梯问题

用线性状态解决爬楼梯问题

爬楼梯是最适合练习一维动态规划建模的例子:每个位置只依赖前两个位置。这里从状态定义开始,推导初始条件和转移方程,再把整张表压缩成两个变量。

学习目标

  • 为线性序列问题定义含义明确的一维状态
  • 从最后一步推导初始条件和状态转移方程
  • 根据有限依赖范围把 O(n)O(n) 空间压缩为 O(1)O(1)

从最后一步定义状态

问题设定为:有 n 级台阶,每次只能上 1 级或 2 级,求到达第 n 级共有多少种走法。

定义 dp[i] 为恰好到达第 i 级台阶的走法数量。到达第 i 级之前,最后一步只有两种可能:从第 i-1 级走 1 级,或者从第 i-2 级走 2 级。因此两类方案互不重叠,可以直接相加:

dp[i]=dp[i−1]+dp[i−2]dp[i]=dp[i-1]+dp[i-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 表和空间压缩版本,便于检查两种实现是否得到相同答案。

python
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))

预期输出

text
[1, 1, 2, 3, 5, 8]
8
8

完整递推表需要保存 n+1 个状态,因此时间复杂度为 O(n)O(n)、空间复杂度为 O(n)O(n)。每个状态只计算一次,所以不会出现朴素递归中重复展开相同子问题的指数级开销。

压缩不再需要的状态

计算 dp[i] 时只读取 dp[i-1] 和 dp[i-2],更早的状态之后不会再参与计算。因此无需保存整张表,只要用 prev1 和 prev2 维护最近两个值即可。

更新两个变量时要注意赋值顺序。Python 的并行赋值会先计算右侧,再统一写回,因此 prev2, prev1 = prev1, prev2 + prev1 不会丢失旧值。在不支持并行赋值的语言中,应使用临时变量保存新状态。

空间压缩后,时间复杂度仍是 O(n)O(n),额外空间降为 O(1)O(1)。这种优化成立的前提不是“DP 表一定能删掉”,而是未来状态只依赖一个固定大小的历史窗口;如果后续转移还需要更早的数据,就必须继续保留那些状态。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用线性状态解决爬楼梯问题

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通