题目链接
LeetCode 面试题 08.01. 三步问题[1]
题目描述
示例1
输入：n = 3 输出：4解释：有四种走法
示例2
输入：n = 5输出：13
题解
昨天的题解地址：
【每日算法Day 79】所有人都会做的入门题，但是能看出你的代码能力！
韦阳的博客：【每日算法Day 79】所有人都会做的入门题，但是能看出你的代码能力！[2]
知乎专栏：【每日算法Day 79】所有人都会做的入门题，但是能看出你的代码能力！[3]
代码
c++
typedeflonglongll;typedefvector<vector<ll>>vvl;typedefvector<ll>vl;constllp=1e9+7; classSolution { public: vvlmat_mul(vvl&A, vvl&B) { inta=A.size(), b=B.size(), c=B[0].size(); vvlC(a, vl(c, 0)); for (inti=0; i<a; ++i) { for (intj=0; j<c; ++j) { for (intk=0; k<b; ++k) { (C[i][j] +=A[i][k] *B[k][j]) %=p; } } } returnC; } vvlmat_pow(vvl&A, intn) { intm=A.size(); vvlB(m, vl(m, 0)); for (inti=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; } returnB; } vvlmat_pow_rec(vvl&A, intn) { if (n==1) returnA; vvlB=mat_pow_rec(A, n/2); B=mat_mul(B, B); if (n&1) returnmat_mul(A, B); returnB; } intwaysToStep(intn) { vlf= {1, 2, 4}; if (n<=3) returnf[n-1]; vvlA= {{0, 0, 1}, {1, 0, 1}, {0, 1, 1}}; vvlB=mat_pow(A, n-3); llres=0; for (inti=0; i<3; ++i) { (res+=f[i] *B[i][2]) %=p; } returnres; } };
python
importnumpyasnpclassSolution: defmat_pow(self, A, n): m=A.shape[0] B=np.eye(m, dtype=np.int64) whilen>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>>=1returnB; defwaysToStep(self, n: int) ->int: self.p=int(1e9+7) f= [1, 2, 4] ifn<=3: returnf[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=0foriinrange(3): res+=f[i] *B[i][2] returnint(res%self.p)
参考资料
[1]
LeetCode 面试题 08.01. 三步问题: https://leetcode-cn.com/problems/three-steps-problem-lcci/
[2]
韦阳的博客：【每日算法Day 79】所有人都会做的入门题，但是能看出你的代码能力！: https://godweiyang.com/2020/03/24/leetcode-inteview-08-01/
[3]
知乎专栏：【每日算法Day 79】所有人都会做的入门题，但是能看出你的代码能力！: https://zhuanlan.zhihu.com/p/115799226
作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
