题目链接
LeetCode 面试题 08.01. 三步问题[1]
题目描述
示例1
输入：n = 3 输出：4解释：有四种走法
示例2
输入：n = 5输出：13
题解
这道题是动态规划入门题，我相信大家都会做，如果不会做，那就当我没说过这句话。
当然了这题太水了，我主要就是想看看大家会怎么实现呢？
代码
定义长度为N 的数组
最朴素的方法当然是定义长度为 的数组，然后算就完事了，代码如下：
typedeflonglongll;constllp=1e9+7;constintN=1e6+10; classSolution { public: llf[N] = {1, 2, 4}; intwaysToStep(intn) { for (inti=3; i<n; ++i) { f[i] = (f[i-1] +f[i-2] +f[i-3]) %p; } returnf[n-1]; } };
定义四个变量
但是这样太费空间了啊，其实每次只需要用到之前的三个状态就行了，然后还要用个临时变量用来交换状态值，代码如下：
typedeflonglongll;constllp=1e9+7; classSolution { public: intwaysToStep(intn) { if (n==1) return1; if (n==2) return2; if (n==3) return4; lla=1, b=2, c=4, d; for (inti=3; i<n; ++i) { d= (a+b+c) %p; a=b; b=c; c=d; } returnd; } };
定义长度为3的数组
typedeflonglongll;constllp=1e9+7; classSolution { public: intwaysToStep(intn) { llf[3] = {1, 2, 4}; for (inti=3; i<n; ++i) { (f[i%3] +=f[(i-1)%3] +f[(i-2)%3]) %=p; } returnf[(n-1)%3]; } };
应读者要求，再来个 python 代码：
classSolution: defwaysToStep(self, n: int) ->int: f= [1, 2, 4] foriinrange(3, n): f[i%3] +=f[(i-1)%3] +f[(i-2)%3] f[i%3] %=1e9+7; returnint(f[(n-1)%3])
参考资料
[1]
LeetCode 面试题 08.01. 三步问题: https://leetcode-cn.com/problems/three-steps-problem-lcci/
简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
