08.01 三步问题

你的名字 2022-10-26 04:58 42阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
    
    示例1:
    
     输入：n = 3 
     输出：4
     说明: 有四种走法
    示例2:
    
     输入：n = 5
     输出：13
    提示:
    
    n范围在[1, 1000000]之间

#### 方案： ####

*  就是个走楼梯问题，选long是因为太大了可能会溢出～

class Solution
    { 
    public:
        int waysToStep(int n)
        { 
            //可能存在int不够用的情况
            if (n == 0)
                return 0;
            vector<long> dp(n + 2, 0);
            dp[0] = 1;
            dp[1] = 1;
            dp[2] = 2;
            long tmp;
    
            for (int i = 3; i < n + 1; i++)
            { 
                tmp = dp[i - 1] + dp[i - 2] + dp[i - 3];
                dp[i] = tmp >= 1000000007 ? tmp % 1000000007 : tmp;
            }
    
            return dp[n] % 1000000007;
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(n)

[Git]: https://github.com/ch98road/leetcode

发表评论取消回复

表情：

评论列表（有 0 条评论，42人围观）

还没有评论，来说两句吧...

相关阅读

相关三步战胜拖延症

请点击上面的“方正柱”，关注我哦????我和我身边的人，或多或少都有一些拖延症存在。我的父母、老婆、孩子，我的几个至交好友，都没有例外。我自己也是一个明显的拖延症患者，直...

朴灿烈づ我的快乐病毒、/ 2024年04月18日 15:35/ 0 赞/ 89 阅读

相关页面设计三步走

摘要作为一个后台类管理系统的开发，经常没有前端开发的人力资源，很多项目不得不自己兼做前端设计和开发。我之前的做法都是直接开始用Axure画原型图，想到什么就画什么，因此

男娘i/ 2023年06月16日 10:35/ 0 赞/ 14 阅读

相关 Leetcode 面试题 08.01. 三步问题

Leetcode 面试题 08.01. 三步问题 1、问题分析 2、问题解决 3、总结 1、问题分析题目链接：[https://leetcod

不念不忘少年蓝@/ 2023年02月11日 03:13/ 0 赞/ 39 阅读

相关三步问题（每日一练）

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

太过爱你忘了你带给我的痛/ 2022年12月25日 11:56/ 0 赞/ 167 阅读

相关 08.01 三步问题

文章目录所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)

你的名字/ 2022年10月26日 04:58/ 0 赞/ 43 阅读

相关一步一步走进Linux HOOK API(三)

一步一步走进Linux HOOK API(三) 经过前两篇的教程,我很郁闷,CSDN的博客发布出来之后,跟我的排版完全不一样了,等这一系列的内容全部完成完成之后,我会发布

川长思鸟来/ 2022年09月25日 00:21/ 0 赞/ 255 阅读

相关一步一步学springboot （十三）集成dubbo

1.用maven管理依赖排除dubbo对spring的依赖 <dependency> <groupId>com.alibaba</groupI

电玩女神/ 2022年06月14日 06:44/ 0 赞/ 294 阅读

相关传统的网络编程（分三步一步一步的写）

server include <sys/types.h> include <sys/socket.h> include <ctype.h>

水深无声/ 2022年05月16日 12:55/ 0 赞/ 272 阅读

相关三步重装系统

第一步：准备U盘，如果有文件就先拷贝下来，不然后面会被格式化。接下来去官网下载windows系统iso文件[https://www.microsoft.com/zh-cn/

逃离我推掉我的手/ 2022年03月07日 16:30/ 0 赞/ 396 阅读

相关一步一步手写promise[三]

上一篇文章我们已经走到差不多最后一步了，只需要处理如果then接受状态的返回值是一个promise，我们递归处理即可。最后的代码长这样： function Pro

港控/mmm°/ 2022年02月13日 08:15/ 0 赞/ 339 阅读