BM63　跳台阶¶

简单通过率 40.65%python3核心代码模式样例通过牛客 AC递归动态规划记忆化搜索

牛客原题　源码

讲解章节：DP 入门

一句话

跳法数就是斐波那契，按最后一步跳了 1 级还是 2 级分类。

解题思路¶

这题考什么¶

计数类 DP 的入门范式：按最后一步分类，把方案集合切成互不重叠且覆盖全部的几块。

状态定义：f[i] = 跳上第 i 级台阶的方法数。最后一步只可能是从第 i-1 级跳 1 级上来，或者从第 i-2 级跳 2 级上来；这两类的完整跳法序列末尾不同，绝不会重复，合起来又穷尽了所有方案，于是可以相加：

f[i] = f[i - 1] + f[i - 2]        (i >= 3)
f[1] = 1, f[2] = 2

形状与斐波那契一致，只是起点错开一位：f[n] = Fib(n + 1)。等价地把 f[0] 定义成 1（「什么都不跳」也算一种方案），递推式对 i >= 2 就统一成立，代码正是按这个约定起手的。转移只依赖前两项，用两个变量滚动，不必开数组。

数据规模与复杂度¶

n <= 40，时限 2 秒（其他语言）。时间 O(n)、空间 O(1)，与题面要求的上界一致。朴素递归 2^40 约 1e12 次调用是唯一会超时的写法。 f[40] = 165580141，不涉及大整数开销。

坑在哪¶

f[2] = 2 而不是 1（跳两次 1 级、直接跳 2 级是两种方案）。照抄斐波那契的 f[1] = f[2] = 1 会让整条数列整体差一位，答案全错。
循环推了 number 次之后，答案在 a 上而不是 b 上：a 起手是 f[0]，推 k 次后 a = f[k]，而 b 已经跑到 f[k+1]。返回错变量就整体多算一级台阶。
f[0] = 1 这个约定必须与题意一致——「站在原地不动」确实是一种合法方案，取 0 会让整条递推塌成全 0。

参考实现¶

solutions/nowcoder/BM63/sol.py
from typing import List, Optional


class Solution:
    def jumpFloor(self, number: int) -> int:
        if number <= 0:
            return 1                # 0 级台阶算 1 种「什么都不跳」的方案，与 f[0] = 1 一致
        # 滚动变量省掉 dp 数组的下标维：转移只回看两格，其余表项算完即弃
        a, b = 1, 1                 # a = f[i-2], b = f[i-1]，取 f[0] = 1, f[1] = 1
        for _ in range(number):     # 推 number 次后 a 恰好停在 f[number]
            a, b = b, a + b         # 右侧同时取旧值，等价于先算 a+b 再整体挪位
        return a                    # 答案在 a 上；b 此刻已经是 f[number+1]

BM63 跳台阶¶