LeetCode 面试题 08.01. 三步问题

约 4 分钟
文章信息 8 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 2-5 程序员面试金典（第 6 版） 微软 滴滴
标签
动态规划 数学 记忆化

题目描述

✅ 面试题 08.01. 三步问题

image-20260928230521068

题意分析

一共有 n 阶台阶，每次能走 1、2 或 3 阶，求恰好走到第 n 阶的走法数量，对 1_000_000_007 取模。走法按步长序列区分，改变先后顺序也可能得到不同方案；题目保证 n >= 1。

解法：滚动 DP

核心思路

[!blue]

令 f(i) 表示走到第 i 阶的方案数。按最后一步分类：最后走一阶的方案，去掉最后一步后恰好对应 f(i - 1)；最后走二阶或三阶时，同理对应 f(i - 2)、f(i - 3)。反过来，给这些旧方案追加对应步长，都能合法到达第 i 阶。

三类的最后一步不同，所以互不重复，又覆盖了所有允许的最后一步。因此有 f(i) = f(i - 1) + f(i - 2) + f(i - 3)。前三项为 f(1) = 1、f(2) = 2、f(3) = 4：第三项包含直接走三阶这一类，不能照搬只能走一、二阶时的初值。

新状态只依赖最近三项，无需保存整个数组。计算第 i 阶之前，保持 a = f(i - 3)、b = f(i - 2)、c = f(i - 1)；先把三者之和存入 d，再更新为 a = b、b = c、c = d。这样下一轮仍能取得连续的前三项，循环结束时 c 就对应第 n 阶。

每次求和后立即取模。加法满足模运算的等价关系，所以只保存各状态的余数不会影响最终余数。虽然每个旧值都小于模数，但三个旧值之和仍可能超过 32 位有符号整数范围，因此 Java 使用 long、Go 使用 int64 承接求和，再取模。

解题步骤

  1. 对 n = 1、2、3 直接返回对应初值。
  2. 用 a = 1、b = 2、c = 4 保存前三个状态。
  3. 从第四阶开始，用宽整数计算 d = (a + b + c) % MOD。
  4. 保存好新值后再滚动三个旧状态，直到处理完第 n 阶，返回 c。

代码实现

// 用滚动变量保留最近三个连续状态。
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)$，每一阶只进行常数次加法、取模和赋值。
  • 空间复杂度：$O(1)$，只保留最近三个状态和一个新状态。

关键点总结

[!green]

  • 按最后一步分类，保证递推不重不漏。
  • 滚动变量在每轮开始时对应连续的前三项，更新顺序必须维持这个含义。
  • 先用宽整数求和再取模，取模值仍可直接参与后续递推。

易错点总结

[!yellow]

  • 求出 d 之前覆盖 a、b、c，会混用不同轮次的状态。
  • 把 f(3) 设为三，会漏掉一次跨三阶的走法。
  • 只在最后取模会导致中间值溢出；只把窄整数相加后的结果赋给宽整数，也无法挽回已经发生的溢出。
  • 题目统计的是有序走法，不能将不同步长顺序合并成一种组合。

相似题目

题目 难度 关联与区别
70. 爬楼梯 简单 原题只允许1或2阶，本题再加入3阶，递推需多保留一个历史状态。
1137. 第 N 个泰波那契数 简单 同样依赖前三项，但计数初值和取模约定不同，不能直接复用泰波那契返回值。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/56793616
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！