上海网络做网站公司,商标起名生成器,服装网站,wordpress windows 伪静态#x1f388;算法那些事专栏说明#xff1a;这是一个记录刷题日常的专栏#xff0c;每个文章标题前都会写明这道题使用的算法。专栏每日计划至少更新1道题目#xff0c;在这立下Flag#x1f6a9; #x1f3e0;个人主页#xff1a;Jammingpro #x1f4d5;专栏链接… 算法那些事专栏说明这是一个记录刷题日常的专栏每个文章标题前都会写明这道题使用的算法。专栏每日计划至少更新1道题目在这立下Flag 个人主页Jammingpro 专栏链接算法那些事 每日学习一点点技术累计看得见 题目
题目描述
三步问题。有个小孩正在上楼梯楼梯有n阶台阶小孩一次可以上1阶、2阶或3阶。实现一种方法计算小孩有多少种上楼梯的方式。结果可能很大你需要对结果模1000000007。
执行示例 示例1: 输入n 3 输出4 说明: 有四种走法 示例2: 输入n 5 输出13 提示
n范围在[1, 1000000]之间
题解
由题目可知爬到第1个台阶的方法数为1种即从起始处爬1步到达爬到第2个台阶的方法数有2种即从开始处爬2步到达或从第1个台阶爬1步到达爬到第3个台阶的方法数有4种即从开始处爬3步到达、从第1个台阶爬2步到达或从第2个台阶爬1步到达…即求爬到第n个台阶的方法数就等于将到达第n个台阶前的3个台阶的方法数相加从而得到状态转移方程为 f ( n ) f ( n − 1 ) f ( n − 2 ) f ( n − 3 ) f(n)f(n-1)f(n-2)f(n-3) f(n)f(n−1)f(n−2)f(n−3)。上面已经知道到达第1到3号台阶的方法数再通过状态转移方程就可以求出第4号台阶及以后台阶的方法数。实现代码如下↓↓↓
class Solution {
public:int waysToStep(int n) {if(n 1) return 1;if(n 2) return 2;const int MOD 1000000007;vectorintdp(n);dp[0] 1;dp[1] 2;dp[2] 4;for(int i 3; i n; i)dp[i] ((dp[i - 1] dp[i - 2]) % MOD dp[i - 3]) % MOD;return dp[n - 1];}
};上面算法的时空复杂度均为O(N)我们可以使用滚动数组的方式将空间复杂度优化为O(1)。我们可以设置四个变量mostpre、ppre、pre、cur分别表示到达n-3、n-2、n-1和n号台阶的方法数。初始状态下mostpre、ppre、pre、cur分别初始化为1、2、4、7即到达第1-4号台阶的方法数。通过mostpreppre、pprepre、precur操作此时mostpre、ppre、pre分别保存到达第2、3、4号台阶的方法数再通过curmostprepprepre可计算出第5号台阶的方法数。以此类推可求出到达后续台阶的方法数实现代码如下↓↓↓
class Solution {
public:int waysToStep(int n) {const int MOD 1000000007;if(n 1) return 1;if(n 2) return 2;if(n 3) return 4;int mostpre 1, ppre 2, pre 4, cur 7;for(int i 4; i n; i){mostpre ppre;ppre pre;pre cur;cur ((mostpre ppre) % MOD pre) % MOD;}return cur;}
};本文存在不足欢迎留言或私信批评、指正。希望我的解决方法能够对你有所帮助~~ 今日打卡完成点亮小星星☆→★
