08.01 三步问题

你的名字 2022-10-26 04:58 62阅读 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 条评论，62人围观）

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

相关阅读

相关三步战胜拖延症

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

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

相关动态规划之三步问题

1. 题目分析题目链接选自力扣 : [三步问题][Link 1] ![image.png][] 根据题中的实力我们来分析, n = 3 时也就是到第 3 个台阶

偏执的太偏执、/ 2024年03月16日 21:31/ 0 赞/ 21 阅读

相关 Ubuntu安装简单三步

第1步：下载Ubuntu 到[https://ubuntu.com/][https_ubuntu.com]上下载Ubuntu镜像文件，我下载的是：ubuntu-18.04.4

左手的ㄟ右手/ 2023年07月23日 03:52/ 0 赞/ 32 阅读

相关页面设计三步走

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

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

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

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

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

相关 spring pagehelper 三步走

<dependency> <groupId>com.gith

青旅半醒/ 2023年02月09日 05:25/ 0 赞/ 22 阅读

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

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

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

相关 08.01 三步问题

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

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

相关三步重装系统

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

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

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

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

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