动态规划是什么？爬楼梯直接递归为什么会慢，滚动数组怎么优化空间？

知识点详解：先解释走法，再写递推

状态不是随便命名的数组格子

dp[n] 不是到第 n 级的最少步数，也不是当前高度，而是走法数量。状态含义变了，转移规则就会不同。

拿 n=3 推一次：路线是 1+1+1、1+2、2+1，一共三种。顺序不同算不同路线，这是题目约定的一部分。可对照 LeetCode 爬楼梯。

如果每次可以上三级，或者某一级不能停留，就必须重新分析，不能照抄两项相加。

按最后一步分组，为什么不会重复？

最后一步是一级的路线，前面必须已经到 n-1；最后一步是两级的路线，前面必须已经到 n-2。

一条路线的最后一步不可能同时是一级和两级，所以两组不重叠。每条合法路线又必然落在其中一组，因此可以直接相加。

这个解释给公式提供了依据，不是因为“像斐波那契”才使用它。相似结果不是推导原因。

dp[0]=1 为什么合理？

我们定义零级台阶有一种空走法：什么都不做。它让 n=2 的公式自然成立，得到从一级再上一阶的一种，以及从零级直接上两阶的一种。

也可以采用从其他基础状态起算的实现，但必须保持语义一致。不能一边把零级写成没有走法，一边在转移里又借它贡献一条路线。

function climbStairs(n: number): number {
  if (!Number.isInteger(n) || n < 0) {
    throw new RangeError("n must be a nonnegative integer");
  }
  if (n === 0) return 1;
  let prev = 1, curr = 1;
  for (let step = 2; step <= n; step++) {
    [prev, curr] = [curr, prev + curr];
  }
  return curr;
}

def climb_stairs(n):
    if type(n) is not int or n < 0:
        raise ValueError("n must be a nonnegative integer")
    if n == 0:
        return 1
    prev, curr = 1, 1
    for step in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

TS 示例适用于结果能被 number 精确表示的范围。更大精确结果应使用 BigInt 等合适方案，而不只是最后把已经失真的 number 转成 BigInt。

图：只求数量，保留前两项。

为什么不用保存整个数组？

算下一项时只依赖最近两项，较早的结果不再参与，因此可以滚动保存。它减少的是状态数量。

如果需要恢复所有路线，或者返回每一级结果，需求就不同。另外，大整数的位数会增长，所以在任意精度模型里，不能把每次加法与实际字节空间都当成固定常数。

递归为什么可能重复计算？

朴素递归会在不同分支里反复求同一个子问题。记忆化保留结果，可以避免这类重复；自底向上的动态规划则按依赖顺序计算。

选择哪种表达，还要看递归深度和状态结构。本文简单一维问题，用迭代更容易明确边界。

面试官继续追问

两变量更新顺序重要吗？

重要。新 curr 需要两个旧值，不能先覆盖 prev 后又把新 prev 当作旧值使用。示例用同时赋值表达。

O(1) 空间是不是永远几个字节？

不是。固定的是保存两个状态；状态值若是不断变大的精确整数，实际存储位数仍增长。

面试速记卡

• 状态：dp[n] 是到第 n 级的走法数量。
• 分组：最后一步一级或两级，互斥且完整。
• 基础：dp[0]=1 表达空走法，dp[1]=1。
• 优化：只求数量时滚动保存前两项。
• 边界：输入约定、大整数精度和运算模型。