LeetCode 面试题 08.01. 三步问题

2022-06-10 HGNULB 约 8 分钟

文章信息 8 个分类 3 个标签

分类

LeetCode CodeTop 简单未解决 2-5 微软滴滴程序员面试金典（第 6 版）

题目描述

✅ 面试题 08.01. 三步问题

题意分析

一个小孩爬 $n$ 阶台阶，每次可以迈 1 阶、2 阶或 3 阶，问一共有多少种不同的上楼方式。这里的「不同」是按顺序区分的：先迈 1 阶再迈 2 阶，和先迈 2 阶再迈 1 阶，算作两种，所以要数的是有序的步长序列，不是「用了几个 1、几个 2、几个 3」的组合。

两个约束信号很重要。第一，$n$ 最大到 $10^6$，这个量级排除了任何指数级枚举，也排除了深度等于 $n$ 的朴素递归（栈会直接爆），只能接受线性甚至更低的迭代做法。第二，题目要求结果对 $1000000007$ 取模，这等于明说答案会大到远超 64 位，取模必须贯穿整个计算过程，不能等到最后。

边界要提前定好：$n=1$ 只有一种走法，$n=2$ 有「1+1」和「2」两种，$n=3$ 有「1+1+1、1+2、2+1、3」四种。这三项要么当初始条件写死，要么保证递推式在它们身上也成立，否则整条递推的地基就是歪的。

解法：滚动 DP

核心思路

先看最直接的想法：写一个递归 f(n) = f(n-1) + f(n-2) + f(n-3)，从 $n$ 一路拆到底。这会形成一棵分支因子为 3 的递归树，时间是指数级的，$n$ 稍微大一点就跑不动；根源在于同一个 f(k) 被从无数条不同路径重复求解。

瓶颈既然是重复子问题，就把它记下来。关键观察在于：到达第 $i$ 阶的最后一步只可能是 1 阶、2 阶或 3 阶，这三种情况互不重叠（最后一步的长度不同）且并集完备（没有第四种可能），所以到达第 $i$ 阶的方案数就是到达第 $i-1$、$i-2$、$i-3$ 阶的方案数之和，而且既不重也不漏。

于是把状态定义写死：$f[i]$ 表示恰好走到第 $i$ 阶的不同走法总数。转移方程为 $f[i]=f[i-1]+f[i-2]+f[i-3]$，初始条件 $f[1]=1$、$f[2]=2$、$f[3]=4$，答案取 $f[n]$。

最后一步优化空间。转移只依赖前三项，前面的历史再也用不到，所以不必开长度为 $n$ 的数组，用三个变量滚动即可，空间从 $O(n)$ 降到 $O(1)$——在 $n$ 达到 $10^6$ 时这不是锦上添花，而是实打实地省掉了几兆内存。

解题步骤

先处理 $n \le 3$ 的情形：$n=1$ 返回 1，$n=2$ 返回 2，$n=3$ 返回 4。为什么必须特判：递推式从 $i=4$ 起才有三个合法的前驱，$i=3$ 时会引用到 $f[0]$，而 $f[0]$ 的含义（空走法算不算一种）容易定错，直接写死这三项最稳妥。

用三个变量 a、b、c 分别持有 $f[i-3]$、$f[i-2]$、$f[i-1]$，初值设为 1、2、4，即 $f[1]$、$f[2]$、$f[3]$。为什么只要三个：转移的依赖窗口宽度就是 3，更早的值不再被任何转移引用。

从 $i=4$ 循环到 $n$，每轮先算 d = (a + b + c) % MOD，再整体右移一格令 a, b, c = b, c, d。为什么要先算再移：三个变量互相依赖，一旦提前覆盖 a，本轮求和用的就是被污染的值。

求和与变量都用 64 位类型承载，并且每轮都取一次模。为什么每轮都取：三个数各自小于 $10^9+7$，加起来接近 $3.1\times 10^9$，早已越过 32 位有符号数的上界；用 64 位承接单轮和是安全的，但若不每轮取模，累积几轮之后连 64 位也会溢出。

循环结束时 c 就是 $f[n]$，转成 32 位返回。为什么可以安全转换：取模后的值一定落在 $[0,\,10^9+6]$，在 int 范围内。

以 n = 5 走一遍：$n>3$，进入循环，初值 $a=f[1]=1$、$b=f[2]=2$、$c=f[3]=4$。第一轮 $i=4$：$d=(1+2+4)\bmod (10^9+7)=7$，也就是 $f[4]=7$；滚动后 $a=2$、$b=4$、$c=7$。第二轮 $i=5$：$d=(2+4+7)\bmod (10^9+7)=13$，即 $f[5]=13$；滚动后 $a=4$、$b=7$、$c=13$。循环结束，返回 $c=13$。可以手工核对 $f[4]=7$：最后一步迈 1 阶接 $f[3]=4$ 种，迈 2 阶接 $f[2]=2$ 种，迈 3 阶接 $f[1]=1$ 种，合计 7 种，与递推一致。

代码实现

// 用滚动数组保留最近三项即可。
class Solution {
    private static final int MOD = 1_000_000_007;

    public int waysToStep(int n) {
        if (n <= 2) {
            return n;
        }
        if (n == 3) {
            return 4;
        }

        long a = 1;
        long b = 2;
        long c = 4;
        for (int i = 4; i <= n; i++) {
            long d = (a + b + c) % MOD;
            a = b;
            b = c;
            c = d;
        }
        return (int) c;
    }
}

// 用滚动数组保留最近三项即可。
func waysToStep(n int) int {
    const mod int64 = 1_000_000_007
    if n <= 2 {
        return n
    }
    if n == 3 {
        return 4
    }

    a, b, c := int64(1), int64(2), int64(4)
    for i := 4; i <= n; i++ {
        d := (a + b + c) % mod
        a, b, c = b, c, d
    }
    return int(c)
}

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 是台阶数。凭据：循环体从 4 跑到 $n$ 共 $n-3$ 轮，每轮只有三次加法、一次取模和三次赋值，全是常数代价。

空间复杂度：$O(1)$，凭据：转移的依赖窗口固定为 3，只需 a、b、c、d 四个标量滚动，不随 $n$ 增长；相比开 $n+1$ 长度的 dp 数组，在 $n=10^6$ 时省下的是数兆内存。

关键点总结

计数型 DP 的转移必须同时满足「不重」和「不漏」。本题按最后一步的长度分类，三类天然互斥且穷尽了全部可能，这是加法能成立的前提；一旦分类标准会让同一条路径被数两次，方程就废了。

状态定义要写成一句完整的中文句子再动手写代码。「$f[i]$ 是走到第 $i$ 阶的走法数」这句话一确定，初始条件填在哪、答案取哪一项、循环从哪开始就都不用猜了。

依赖窗口有多宽就留多少个变量。凡是「只依赖前 $k$ 项」的递推都能滚动压到 $O(k)$ 空间，这个套路对斐波那契、爬楼梯、打家劫舍一整类题通用。

滚动更新要么用一行元组赋值，要么先把新值算进临时量再整体右移；千万别边算边覆盖。

面试视角：题目给了取模就等于给了提示——答案会爆 64 位。能主动说出「每轮取模而非最后取模」以及「三个模数相加要用 64 位承接」，比写对递推式更能体现工程素养。

面试视角：$n$ 到 $10^6$ 时线性解法已经够用，但面试官常追问能不能更快。标准回答是构造 $3\times 3$ 的转移矩阵做快速幂，把时间压到 $O(\log n)$；若追问递归写法，则要指出深度 $10^6$ 的递归在默认栈大小下必然溢出，必须改迭代或手动开大栈。

易错点总结

错误写法：用 32 位 int 承接 a + b + c 再取模。用例 $n$ 较大使三项都逼近 $10^9$ → 和接近 $3.1\times 10^9$ 超过 int 上界，回绕成负数，取模后得到负的方案数。

错误写法：整个循环跑完才对结果取一次模。用例 $n=100$ → 方案数增长约为每步三倍，几十轮之后连 64 位都装不下，最终值完全是溢出后的垃圾。

错误写法：初始条件写成 $f[1]=1,\ f[2]=1,\ f[3]=2$，套用爬楼梯的记法。用例 $n=4$ → 递推得 $1+1+2=4$，而正确答案是 7，整条序列从第四项起全错。

错误写法：不特判 $n\le 3$，直接让循环从 $i=3$ 起并用 $f[0]=1,f[1]=1,f[2]=2$ 起步却把 $f[0]$ 当成 0。用例 $n=3$ → 得到 $0+1+2=3$，漏掉了「一步迈 3 阶」这种走法，正确答案是 4。

错误写法：滚动时写成 a = b; b = c; c = a + b + c;。用例 a=1,b=2,c=4 → 前两行已把 a 改成 2、b 改成 4，第三行算出 $2+4+4=10$ 而非 7，从此每一项都偏大。

错误写法：把方案数当成组合数，认为「1+2」和「2+1」是同一种。用例 $n=3$ → 只数出 {1,1,1}、{1,2}、{3} 三种，比正确的 4 少一种，$n$ 越大差距越悬殊。

错误写法：用无记忆化的朴素递归。用例 $n=40$ → 递归树分支因子为 3，节点数达到 $10^{19}$ 量级，直接超时；即使加了记忆化，$n=10^6$ 的递归深度也会先把调用栈压爆。

错误写法：开数组时写成 new int[n] 然后访问 dp[n]。用例 $n=5$ → 合法下标只到 4，访问 dp[5] 直接数组越界；状态下标从 1 编号时数组长度必须是 $n+1$。

错误写法：模数敲成 $10^9+9$ 或写成 1e9 + 7 这样的浮点字面量。用例任意较大的 $n$ → 前者整条结果偏移，后者在部分语言里引入浮点转换导致精度丢失，两种都是判题时才发现的隐形错误。

错误写法：返回时把已取模的 64 位值再做一次 % MOD 却忘了它可能是负数（若中途用了减法或错误类型）。用例任何中途溢出成负数的情形 → 语言的取模会保留负号，返回负的方案数；稳妥做法是统一 (x % MOD + MOD) % MOD。

相似题目

题目	难度	考察点
70. 爬楼梯	简单	依赖窗口缩到 2，不涉及取模
509. 斐波那契数	简单	递推的最小骨架，用于对比初始条件的差别
746. 使用最小花费爬楼梯	简单	从计数改成求最小代价，加法换成取最小值
LCR 088. 使用最小花费爬楼梯	简单	同上题换皮，可练习起点终点的两种约定
剑指 Offer 10- I. 斐波那契数列	简单	同样要求逐步取模，重点在防溢出
剑指 Offer 10- II. 青蛙跳台阶问题	简单	步长只有 1 和 2，注意 $n=0$ 的初始值约定
补充题 2. 圆环回原点问题	中等	状态多一维位置，转移在环上左右两个方向