面试题 08.01 三步问题：doocs/leetcode 中线性递推与矩阵快速幂的多语言题解指南

三步问题是《程序员面试金典（第 6 版）》中的经典动态规划入门题：一个小孩每次可上 1、2 或 3 阶台阶，需要统计上完 n 阶楼梯的全部走法，并对结果取模 1000000007。本文以 doocs/leetcode 仓库中 lcci/08.01.Three Steps Problem/README.md 题解文档为核心骨架，结合仓库内 13 份多语言 Solution 源码，系统讲解「三阶斐波那契式递推」的两种解法：O(n) 滚动变量递推与 O(log n) 矩阵快速幂，并给出 Python3、Java、C++、Go、Rust、JavaScript、C、Swift 八种语言的完整可直接运行的实现。读完本文，你将掌握递推公式的推导、取模溢出的处理技巧，以及如何用矩阵快速幂把线性递推从 O(n) 加速到 O(log n)。

题目背景与约束

题目原文（见 README.md）描述如下：

三步问题。有个小孩正在上楼梯，楼梯有 n 阶台阶，小孩一次可以上 1 阶、2 阶或 3 阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模 1000000007。

关键约束有三点，决定了解法选型：

• 走法定义：每一步的步长只能是 1、2 或 3 阶，即上到第 i 阶的最后一步只能来自第 i-1、i-2 或 i-3 阶；
• 取模要求：结果可能很大，必须对 1000000007（即 10^9 + 7，一个质数）取模；
• 数据范围：n 在 [1, 1000000] 之间。n 可达 10^6，方案数会以指数级增长（约等于三阶斐波那契数列），不取模会瞬间溢出，这也是题目强制取模的原因。

官方给出的两个示例：

输入	输出	说明
n = 3	4	四种走法：(1,1,1)、(1,2)、(2,1)、(3)
n = 5	13	全部合法走法共 13 种

英文版题解见 README_EN.md。

核心思路：从三路递归到线性递推

朴素递归为什么不行

若直接按「每次上 1、2 或 3 阶」三路展开递归而不做记忆化，计算 f(n) 会反复求解大量相同的子问题，复杂度接近指数级。正如题解中「思考」注记所指出的：

递归按三路展开而不记忆，重复子问题极多。

状态定义与递推公式

定义 f[i] 表示上到第 i 阶台阶的方法数。由于最后一步只能是 1、2 或 3 阶，到达第 i 阶的方案数等于到达前三个台阶方案数之和：

f[i] = f[i-1] + f[i-2] + f[i-3]

边界初始值：

• f[1] = 1：只走 1 阶，一种走法；
• f[2] = 2：可 (1,1) 或 (2)，两种走法；
• f[3] = 4：可 (1,1,1)、(1,2)、(2,1)、(3)，四种走法。

答案即为 f[n]。这与经典斐波那契数列 f[i] = f[i-1] + f[i-2] 同源，只是递推阶数从二阶扩展为三阶（常称 Tribonacci 型递推）。

方法一：滚动变量递推（O(n) 时间，O(1) 空间）

由于 f[i] 只依赖 f[i-1]、f[i-2]、f[i-3]，无需开辟长度为 n 的数组，只需三个变量 a、b、c 滚动保存最近三项即可。以 a, b, c = 1, 2, 4 初始化，每轮迭代更新为 a = b, b = c, c = (a + b + c) % mod，循环 n - 1 次后 a 即为 f(n)。时间复杂度 O(n)，空间复杂度 O(1)。

题解文档（README.md）中给出了 8 种语言的完整实现，仓库中对应的独立源码文件为 Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.js、Solution.rs、Solution.swift、Solution.c（见 lcci/08.01.Three Steps Problem 目录）。

Python3

源码见 Solution.py：

class Solution:
    def waysToStep(self, n: int) -> int:
        a, b, c = 1, 2, 4
        mod = 10**9 + 7
        for _ in range(n - 1):
            a, b, c = b, c, (a + b + c) % mod
        return a

Java

源码见 Solution.java。注意 Java 的 int 最大值为 2^31-1，若先求和再取模可能溢出，因此每一步都及时取模：

class Solution {
    public int waysToStep(int n) {
        final int mod = (int) 1e9 + 7;
        int a = 1, b = 2, c = 4;
        for (int i = 1; i < n; ++i) {
            int t = a;
            a = b;
            b = c;
            c = (((a + b) % mod) + t) % mod;
        }
        return a;
    }
}

C++

源码见 Solution.cpp：

class Solution {
public:
    int waysToStep(int n) {
        const int mod = 1e9 + 7;
        int a = 1, b = 2, c = 4;
        for (int i = 1; i < n; ++i) {
            int t = a;
            a = b;
            b = c;
            c = (((a + b) % mod) + t) % mod;
        }
        return a;
    }
};

Go

源码见 Solution.go。Go 支持多重赋值，写法最简洁：

func waysToStep(n int) int {
	const mod int = 1e9 + 7
	a, b, c := 1, 2, 4
	for i := 1; i < n; i++ {
		a, b, c = b, c, (a+b+c)%mod
	}
	return a
}

Rust

源码见 Solution.rs：

impl Solution {
    pub fn ways_to_step(n: i32) -> i32 {
        let (mut a, mut b, mut c) = (1, 2, 4);
        let m = 1000000007;
        for _ in 1..n {
            let t = a;
            a = b;
            b = c;
            c = (((a + b) % m) + t) % m;
        }
        a
    }
}

JavaScript

源码见 Solution.js：

/**
 * @param {number} n
 * @return {number}
 */
var waysToStep = function (n) {
    let [a, b, c] = [1, 2, 4];
    const mod = 1e9 + 7;
    for (let i = 1; i < n; ++i) {
        [a, b, c] = [b, c, (a + b + c) % mod];
    }
    return a;
};

C

源码见 Solution.c：

int waysToStep(int n) {
    const int mod = 1e9 + 7;
    int a = 1, b = 2, c = 4;
    for (int i = 1; i < n; ++i) {
        int t = a;
        a = b;
        b = c;
        c = (((a + b) % mod) + t) % mod;
    }
    return a;
}

Swift

源码见 Solution.swift。Swift 版本额外加入了 n=1、2、3 的提前返回分支，逻辑更显式：

class Solution {
    func waysToStep(_ n: Int) -> Int {
        let mod = Int(1e9) + 7
        var a = 1, b = 2, c = 4
        if n == 1 { return a }
        if n == 2 { return b }
        if n == 3 { return c }

        for _ in 1..<n {
            let t = a
            a = b
            b = c
            c = ((a + b) % mod + t) % mod
        }
        return a
    }
}

实现要点小结

• 取模时机：递推中每步都对 (a + b + c) % mod 取模，避免中间结果溢出；Java/C++/C 中还要注意 (a + b) % mod 先行取模再加 t；
• 循环次数：三种写法分别用 range(n-1)（Python）、i < n（Java/C++/C）、1..n（Rust/Swift），效果等价——从初始三元组出发滚动 n-1 次；
• 空间收益：相比数组 DP，滚动变量将空间从 O(n) 降到 O(1)，对 n=10^6 的规模尤为关键。

方法二：矩阵快速幂加速递推（O(log n) 时间，O(1) 空间）

当 n 进一步增大时，O(n) 的线性扫描仍要执行 n 次模运算。三阶常系数递推可以写成「状态向量 × 转移矩阵」的形式，再用矩阵快速幂在 O(log n) 次矩阵乘法内求得 F(n)。题解中对该方法有清晰的推导过程。

状态向量与转移矩阵的推导

定义 F(n) 表示 1×3 矩阵：

F(n) = [ F(n-1)  F(n-2)  F(n-3) ]

我们希望由 F(n-1) = [ F(n-2) F(n-3) F(n-4) ] 推出 F(n)，即寻找矩阵 base 满足：

[ F(n-2)  F(n-3)  F(n-4) ] × base = [ F(n-1)  F(n-2)  F(n-3) ]

由于 F(n) = F(n-1) + F(n-2) + F(n-3)，可验证转移矩阵为：

base = [ 1 1 0 ]
       [ 1 0 1 ]
       [ 1 0 0 ]

初始矩阵取 res = [ 4 2 1 ]（即 f(3)、f(2)、f(1)），那么 F(n) 等于 res 乘以 base^(n-4) 后结果矩阵中所有元素之和。用矩阵快速幂计算 base^(n-4)，时间复杂度 O(log n)，空间复杂度 O(1)。

题解文档中给出了 Python3（numpy）、Java、C++、Go、JavaScript 五种实现，仓库对应的独立源码为 Solution2.py、Solution2.java、Solution2.cpp、Solution2.go、Solution2.js。

Python3（numpy）

源码见 Solution2.py。这里使用 numpy 的 asmatrix 配合对象类型 np.dtype("O") 做逐元素取模；n < 4 时直接返回 2^(n-1)（f(1)=1、f(2)=2、f(3)=4 恰好符合）：

import numpy as np


class Solution:
    def waysToStep(self, n: int) -> int:
        if n < 4:
            return 2 ** (n - 1)
        mod = 10**9 + 7
        factor = np.asmatrix([(1, 1, 0), (1, 0, 1), (1, 0, 0)], np.dtype("O"))
        res = np.asmatrix([(4, 2, 1)], np.dtype("O"))
        n -= 4
        while n:
            if n & 1:
                res = res * factor % mod
            factor = factor * factor % mod
            n >>= 1
        return res.sum() % mod

Java

源码见 Solution2.java。手写 mul（矩阵乘）与 pow（快速幂），矩阵元素用 long 承载并逐步取模，避免乘法溢出：

class Solution {
    private final int mod = (int) 1e9 + 7;

    public int waysToStep(int n) {
        if (n < 4) {
            return (int) Math.pow(2, n - 1);
        }
        long[][] a = {{1, 1, 0}, {1, 0, 1}, {1, 0, 0}};
        long[][] res = pow(a, n - 4);
        long ans = 0;
        for (long x : res[0]) {
            ans = (ans + x) % mod;
        }
        return (int) ans;
    }

    private long[][] mul(long[][] a, long[][] b) {
        int m = a.length, n = b[0].length;
        long[][] c = new long[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int k = 0; k < b.length; ++k) {
                    c[i][j] = (c[i][j] + a[i][k] * b[k][j] % mod) % mod;
                }
            }
        }
        return c;
    }

    private long[][] pow(long[][] a, int n) {
        long[][] res = {{4, 2, 1}};
        while (n > 0) {
            if ((n & 1) == 1) {
                res = mul(res, a);
            }
            a = mul(a, a);
            n >>= 1;
        }
        return res;
    }
}

C++

源码见 Solution2.cpp：

class Solution {
public:
    int waysToStep(int n) {
        if (n < 4) {
            return pow(2, n - 1);
        }
        vector<vector<ll>> a = {{1, 1, 0}, {1, 0, 1}, {1, 0, 0}};
        vector<vector<ll>> res = qpow(a, n - 4);
        ll ans = 0;
        for (ll x : res[0]) {
            ans = (ans + x) % mod;
        }
        return ans;
    }

private:
    using ll = long long;
    const int mod = 1e9 + 7;
    vector<vector<ll>> mul(vector<vector<ll>>& a, vector<vector<ll>>& b) {
        int m = a.size(), n = b[0].size();
        vector<vector<ll>> c(m, vector<ll>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int k = 0; k < b.size(); ++k) {
                    c[i][j] = (c[i][j] + a[i][k] * b[k][j] % mod) % mod;
                }
            }
        }
        return c;
    }

    vector<vector<ll>> qpow(vector<vector<ll>>& a, int n) {
        vector<vector<ll>> res = {{4, 2, 1}};
        while (n) {
            if (n & 1) {
                res = mul(res, a);
            }
            a = mul(a, a);
            n >>= 1;
        }
        return res;
    }
};

Go

源码见 Solution2.go：

const mod = 1e9 + 7

func waysToStep(n int) (ans int) {
	if n < 4 {
		return int(math.Pow(2, float64(n-1)))
	}
	a := [][]int{{1, 1, 0}, {1, 0, 1}, {1, 0, 0}}
	res := pow(a, n-4)
	for _, x := range res[0] {
		ans = (ans + x) % mod
	}
	return
}

func mul(a, b [][]int) [][]int {
	m, n := len(a), len(b[0])
	c := make([][]int, m)
	for i := range c {
		c[i] = make([]int, n)
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			for k := 0; k < len(b); k++ {
				c[i][j] = (c[i][j] + a[i][k]*b[k][j]%mod) % mod
			}
		}
	}
	return c
}

func pow(a [][]int, n int) [][]int {
	res := [][]int{{4, 2, 1}}
	for n > 0 {
		if n&1 == 1 {
			res = mul(res, a)
		}
		a = mul(a, a)
		n >>= 1
	}
	return res
}

JavaScript

源码见 Solution2.js。JS 的 Number 精度有限，乘法会溢出，因此 mul 内部用 BigInt 完成乘法与取模后再转回 Number：

/**
 * @param {number} n
 * @return {number}
 */

const mod = 1e9 + 7;

var waysToStep = function (n) {
    if (n < 4) {
        return Math.pow(2, n - 1);
    }
    const a = [
        [1, 1, 0],
        [1, 0, 1],
        [1, 0, 0],
    ];
    let ans = 0;
    const res = pow(a, n - 4);
    for (const x of res[0]) {
        ans = (ans + x) % mod;
    }
    return ans;
};

function mul(a, b) {
    const [m, n] = [a.length, b[0].length];
    const c = Array.from({ length: m }, () => Array.from({ length: n }, () => 0));
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            for (let k = 0; k < b.length; ++k) {
                c[i][j] =
                    (c[i][j] + Number((BigInt(a[i][k]) * BigInt(b[k][j])) % BigInt(mod))) % mod;
            }
        }
    }
    return c;
}

function pow(a, n) {
    let res = [[4, 2, 1]];
    while (n) {
        if (n & 1) {
            res = mul(res, a);
        }
        a = mul(a, a);
        n >>= 1;
    }
    return res;
}

矩阵快速幂要点

• 指数边界：n < 4 时直接返回 2^(n-1)，避免出现负数指数；否则幂次为 n - 4；
• 初始矩阵：res = [4, 2, 1] 对应 f(3)、f(2)、f(1)，这是与二阶斐波那契矩阵解法（初始为 [f(2), f(1)]）的重要区别；
• 结果聚合：最终答案取 res × base^(n-4) 首行三元素之和再取模；
• 溢出防护：矩阵乘法每步 % mod；JS 必须借助 BigInt，Java/C++/Go 使用 64 位整数类型。

两种解法对比与选型

维度	方法一：滚动变量递推	方法二：矩阵快速幂
时间复杂度	O(n)	O(log n)
空间复杂度	O(1)	O(1)
实现复杂度	极低，几行代码	较高，需手写矩阵乘法与快速幂
适用场景	n ≤ 10^6（本题官方范围）	n 极大、单次查询或多查询时

从仓库实现看，两种方法都验证了「结果取模」与「状态只依赖最近三项」这两个核心性质。对于本题 n ≤ 1000000 的约束，方法一已经足够且实现最简洁；方法二则是 n 扩展到更大数量级时的通用优化方案，其「递推 → 矩阵 → 快速幂」的套路可复用于任意 k 阶常系数线性递推。

仓库源码速览

本题题解及源码统一存放于 lcci/08.01.Three Steps Problem 目录下：

• 题解文档：README.md（中文）、README_EN.md（英文）
• 方法一源码：Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.js、Solution.rs、Solution.swift、Solution.c
• 方法二源码：Solution2.py、Solution2.java、Solution2.cpp、Solution2.go、Solution2.js

各语言源码与题解文档中的代码块一一对应，可直接复制运行。该题属于 lcci（程序员面试金典）题集，仓库还收录了同类型的线性递推取模题（如 面试题10- I. 斐波那契数列），可作为对比练习。若需在本机验证，可结合仓库根目录的 package.json 与 requirements.txt 准备对应语言的运行环境（Python 版矩阵解法需安装 numpy）。