LeetCode 70. 爬楼梯：动态规划的第一课

题目：为什么爬楼梯是 DP

LeetCode 70：你在爬 n 阶楼梯，每次可以爬 1 或 2 个台阶，问有多少种不同的方法到达楼顶。

输入：n = 3
输出：3（1+1+1、1+2、2+1）

为什么这题是 DP：「到达第 n 阶的方法数」与「到达第 n-1 阶的方法数」有关——最后一步只有两种可能：从 n-1 阶跨 1 步、或从 n-2 阶跨 2 步——「到达 n 的方法数 = 到达 n-1 的方法数 + 到达 n-2 的方法数」——这就是状态转移方程——而它恰好是斐波那契数列。

四个版本的演进：DP 思想的完整演示

版本一：暴力递归 O(2ⁿ)。直接翻译递推关系：

def climb_stairs(n):                      # O(2^n) —— 超时
    if n <= 2:
        return n
    return climb_stairs(n-1) + climb_stairs(n-2)

为什么是 O(2ⁿ)：递归树展开——f(5) 调 f(4) 和 f(3)，f(4) 调 f(3) 和 f(2)——「f(3) 被算了两次」——递归树呈指数展开——「重复子问题」——同一个子问题被反复求解——「重复子问题」是 DP 存在的理由——发现它，是 DP 思维的第一步。

版本二：记忆化递归 O(n)。算过的存起来——「memo」：

def climb_stairs(n, memo=None):
    if memo is None:
        memo = {}
    if n <= 2:
        return n
    if n in memo:
        return memo[n]
    memo[n] = climb_stairs(n-1, memo) + climb_stairs(n-2, memo)
    return memo[n]

「每个子问题只算一次」——O(n) 个子问题 × 每个一次 O(1) = O(n)——「空间换时间」——memo 的 O(n) 空间——记忆化递归与 DP 的关系：「DP 是把记忆化递归改成迭代」——本质完全相同（都是缓存子问题），形态不同。

版本三：DP 数组（自底向上）O(n) 时间 O(n) 空间。把递归「自顶向下」翻转为「自底向上」——先算 f(1)、f(2)，再递推 f(3)、f(4)……：

def climb_stairs(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

「自底向上」的优点：无递归（无栈溢出风险）、循环可优化（「递推的方向」可以调整——有的题自底向上还能降维。「DP 数组的含义」要能说清楚——dp[i] = 到达第 i 阶的方法数——「能说清 dp[i] 的含义」是 DP 不写错的根本。

版本四：滚动变量 O(n) 时间 O(1) 空间。观察：dp[i] 只依赖 dp[i-1] 和 dp[i-2]——「更早的历史」完全没用——不需要存整个数组——两个变量滚动：

def climb_stairs(n):
    if n <= 2:
        return n
    prev, curr = 1, 2                    # dp[i-2], dp[i-1]
    for _ in range(3, n + 1):
        prev, curr = curr, prev + curr
    return curr

「滚动变量」是 DP 空间优化的通用技巧——「依赖范围」决定可否降维（只依赖前 2 项 → 2 个变量；依赖前一行 → 一行数组——「空间优化」在 01 背包中的经典应用（倒序遍历）——爬楼梯是它的最简形态。

graph TD
    A[版本 1: 暴力递归 O(2^n)<br/>重复子问题] --> B[版本 2: 记忆化 O(n)<br/>缓存子问题]
    B --> C[版本 3: DP 数组 O(n)<br/>自底向上 无递归]
    C --> D[版本 4: 滚动变量 O(1) 空间<br/>只留最近依赖]

DP 的三个核心概念（以爬楼梯为锚）

概念一：状态定义——dp[i] 是什么——「到达第 i 阶的方法数」——状态定义是 DP 的地基——定义错了（比如定义成「当前所在阶」）全盘皆错——「状态定义的常见陷阱」：定义成「过程」而非「结果」——「dp[i] 要回答一个完整的问题」。概念二：状态转移方程——dp[i] 如何从更小的状态推出——「最后一步的拆解」（爬楼梯的「最后一步是 1 或 2」——「枚举最后一步」是推导转移方程的万能起手式——几乎所有线性 DP 都能这么推（打家劫舍篇的「最后一步偷或不偷」）。概念三：边界与初始化——dp[1] = 1、dp[2] = 2——「边界是递推的起点」——初始化错一格全盘皆错——「边界对应最小的不可再分的问题」。

「DP 是带记忆的递归」这句话的真正含义：递归定义了问题的结构（分而治之）、记忆消除了重复（子问题缓存）、迭代消除了递归（自底向上）——「三者是同一个思想的三种实现」——理解了这个统一性，DP 就不再是「玄学」而是「缓存重复计算的工程实践」——与两数之和的哈希表呼应：哈希缓存「查过的值」、memo 缓存「算过的子问题」——「空间换时间」的家族再添一员。

爬楼梯的进阶：DP 的识别与「从递推到方程」

爬楼梯的进阶：DP 问题的识别方法论与「从暴力到方程」的系统路径。「DP 问题的识别」：「DP 的三个信号」：信号一「求最值/方案数」（最大化、最小化、多少种——「最值/计数」的信号）；信号二「可分解为子问题」（大问题的解由小问题的解构成——「可分解性」）；信号三「无后效性」（未来与过去无关——「无后效性」的定义（当前状态确定后，后续决策不依赖路径——「无后效性」是 DP 的合法性前提——「有后效性」的处理（扩展状态（把路径信息编入状态——「状态的设计」消除后效性——「无后效性」的实例（路径问题（位置+方向——「方向编入状态」的修复。「从暴力到方程」的系统路径：「五步法」：步骤一「定义暴力解法」（枚举所有可能——「暴力」的确认（正确性基线）；步骤二「找重复子问题」（暴力树中的重复节点——「画递归树」找重复；步骤三「定义状态」（子问题的精确描述——「状态的参数」（爬楼梯是 n、编辑距离是双串下标——「参数的选择」决定维度；步骤四「写转移方程」（状态之间的关系——「转移的推导」从暴力解法的最后一步——「枚举最后一步」的万能起手——步骤五「确定边界与顺序」（递推的方向——「五步法」的通用性——「五步法」在复杂 DP（编辑距离）的验证——「方法论」的价值在于可复用。「DP 的空间优化谱系」：「降维的条件」：「依赖范围」（dp[i] 依赖哪些——「一维依赖」→ 滚动变量——「二维依赖」→ 行滚动——「背包的倒序」（一维化的倒序——「滚动数组」（两行交替——「位运算滚动」（「滚动」的极致——「空间优化的清单」——「优化是最后一步」——先写对、再优化——「先正确后优化」的纪律。爬楼梯的进阶总结：DP 识别的三信号（最值/计数、可分解、无后效性）+五步法（暴力→重复→状态→转移→边界）+空间优化谱系（滚动变量/行滚动/倒序）——「爬楼梯」的价值在于它是「DP 方法论的微缩沙盘」——「五个版本的演进」对应「五步法」的落地——「方法论驱动的刷题」优于「题海驱动」——**「做一道题，掌握一套方法」——爬楼梯就是那套方法的第一块拼图。

爬楼梯的高频问答：大数加速、边界差异与变体推广

问题一：n 特别大（比如 10¹⁸）怎么办？DP 数组存不下也跑不动。——斐波那契型递推自带「加速器」：矩阵快速幂。f(n) = f(n−1) + f(n−2) 可以写成二阶矩阵 [[1,1],[1,0]] 的幂，矩阵幂用快速幂计算，总复杂度从 O(n) 降到 O(log n)——十亿阶楼梯只要约三十次矩阵乘法。题目若要求结果取模（数值可能是天文数字），每步乘法后取模即可，复杂度不变。还有一个冷知识是皮萨诺周期：斐波那契数列模 m 的结果是周期性的（模 10ᵏ 的周期是 15×10ᵏ⁻¹），超大 n 可以先对周期取余、再算小规模。LeetCode 70 的 n ≤ 45 完全用不上这些，但「楼梯有一亿阶」是面试常见的追问场景——「递推线性」到「矩阵对数」是同一思想的复杂度跃迁，知道这条路的存在本身就是加分项。

问题二：爬楼梯和斐波那契到底差在哪？为什么我总差一位？——数列本体相同，边界定义差一档：标准斐波那契 F(1)=1、F(2)=1；爬楼梯 dp[1]=1、dp[2]=2——对应关系是 dp[n] = F(n+1)。出错几乎都出在初始化而不是转移：转移方程两边一模一样。应对办法是把边界还原成题意而不是背数字：dp[1] 是「一步到达」只有 1 种爬法、dp[2] 是「两步到达」有 1+1 与 2 两种——从语义推出边界，永远不会差一位。这也是 DP 的通用纪律：每个边界值都要能对最小实例手工验证——n=1、n=2 各走一遍，验证不过的初始化一定是错的。「差一位」的病根从来不在公式，在「边界没有过题意这一关」。

问题三：规则变了怎么办——每次可以爬 1、2、3 步？某些台阶禁踩？每步还有花费（LeetCode 746）？——三个变体检验同一个框架的三个部件。转移方程：1/2/3 步就是 dp[i] = dp[i−1] + dp[i−2] + dp[i−3]——「枚举最后一步」多枚举一项，框架纹丝不动。可达性：禁踩的台阶置为不可达，转移时跳过不可达的前驱——状态从「方法数」变成「能否到达」，正好是可行性 DP 的形态。优化目标：746 最小花费爬楼梯把「计数」换成「最小化」：dp[i] = cost[i] + min(dp[i−1], dp[i−2])——注意它的一个坑：楼顶在最后一个台阶之外，答案取 min(dp[n−1], dp[n−2])，直接返回 dp[n−1] 是 746 最常见的错。三个变体共用「状态定义 → 枚举最后一步 → 边界验证」的路径——爬楼梯真正的遗产是这条路径本身，规则怎么变，路径不变。

小结

爬楼梯的完整演进：暴力递归 O(2ⁿ)（重复子问题的暴露）→ 记忆化 O(n)（缓存子问题）→ DP 数组（自底向上、无递归）→ 滚动变量 O(1)（依赖范围的压缩）；DP 三概念（状态定义是地基——dp[i] 要回答完整问题、转移方程靠「枚举最后一步」推导、边界对应最小不可分问题）；思想统一（DP = 记忆化递归 = 缓存重复计算的工程实践——与哈希表的「空间换时间」同族）。给初学者的方法论：学 DP 就把爬楼梯的四个版本亲手写一遍——写完你会拥有一张「DP 思想地图」：任何 DP 题先问三个问题——「状态是什么、怎么转移、边界在哪」——然后从记忆化递归开始写（它最接近直觉），再机械地转成 DP 数组，最后看能否降维——「从记忆化到 DP」的机械转换是初学者的最佳路径——等这条路径走熟了，你就能跳过中间步骤直接写 DP。

爬楼梯教会你的不是「爬楼梯」，是「重复子问题的识别与消灭」——这个思想从斐波那契一路延伸到编辑距离、背包问题、直到强化学习的 Bellman 方程——DP 的世界，从这一阶楼梯开始。