题目链接
LeetCode 面试题 08.01. 三步问题[1]
题目描述
三步问题。有个小孩正在上楼梯，楼梯有 阶台阶，小孩一次可以上 阶、 阶或 阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模 。
示例1
输入： n = 3 输出： 4 解释： 有四种走法
示例2
输入： n = 5 输出： 13
题解
昨天的题解地址：
【每日算法Day 79】所有人都会做的入门题，但是能看出你的代码能力！
韦阳的博客：【每日算法Day 79】所有人都会做的入门题，但是能看出你的代码能力！[2]
知乎专栏：【每日算法Day 79】所有人都会做的入门题，但是能看出你的代码能力！[3]
昨天是通过动态规划来解决的，转移方程为：
初始情况是 。
如果通过递推的方式来求解的话，时间复杂度是 ，但是我们还可以用矩阵快速幂的方法加速到 。
相信大家快速幂一定听说过（没听说过当我没说），如果让你求 ，那么可以分两种情况。如果 是偶数，那么可以计算 ，然后求它的平方 就行了。如果 是奇数，那么可以计算 ，然后求它的平方 就行了。这样只需要用 的复杂度就可以计算出 了。
类似的，如果我们要计算一个矩阵的幂 ，也可以将其拆分成两半，然后计算一半再平方就行了。
那么这题跟矩阵有什么关系呢？如果我们把转移方程右边三项写成向量形式：
那么给它右边乘上一个矩阵 ：
那么就会得到向量：
即：
所以乘一次矩阵 就可以得到下一个 值，那么从初始的向量 开始，乘上 就可以得到 了。
而这里的 就可以通过矩阵快速幂来计算得到。
代码
c++
typedef long long ll; typedef vector<vector<ll>> vvl; typedef vector<ll> vl; const ll p = 1e9+7; class Solution { public: vvl mat_mul(vvl& A, vvl& B) { int a = A.size(), b = B.size(), c = B[0].size(); vvl C(a, vl(c, 0)); for (int i = 0; i < a; ++i) { for (int j = 0; j < c; ++j) { for (int k = 0; k < b; ++k) { (C[i][j] += A[i][k] * B[k][j]) %= p; } } } return C; } vvl mat_pow(vvl& A, int n) { int m = A.size(); vvl B(m, vl(m, 0)); for (int i = 0; i < m; ++i) B[i][i] = 1; while (n > 0) { if (n&1) B = mat_mul(B, A); A = mat_mul(A, A); n >>= 1; } return B; } vvl mat_pow_rec(vvl& A, int n) { if (n == 1) return A; vvl B = mat_pow_rec(A, n/2); B = mat_mul(B, B); if (n&1) return mat_mul(A, B); return B; } int waysToStep(int n) { vl f = {1, 2, 4}; if (n <= 3) return f[n-1]; vvl A = {{0, 0, 1}, {1, 0, 1}, {0, 1, 1}}; vvl B = mat_pow(A, n-3); ll res = 0; for (int i = 0; i < 3; ++i) { (res += f[i] * B[i][2]) %= p; } return res; } };
python
import numpy as np class Solution: def mat_pow(self, A, n): m = A.shape[0] B = np.eye(m, dtype=np.int64) while n > 0: if (n&1)!=0: B = np.mod(np.matmul(B, A), self.p).astype(np.int64) A = np.mod(np.matmul(A, A), self.p).astype(np.int64) n >>= 1 return B; def waysToStep(self, n: int) -> int: self.p = int(1e9+7) f = [1, 2, 4] if n <= 3: return f[n-1] A = np.array([[0, 0, 1], [1, 0, 1], [0, 1, 1]], dtype=np.int64) B = self.mat_pow(A, n-3) res = 0 for i in range(3): res += f[i] * B[i][2] return int(res%self.p)
