青蛙跳台阶问题

电玩女神 2022-12-27 01:48 151阅读 0赞

> [剑指 Offer 10 \[easy\]][Offer 10 _easy]  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70]

### 题解 ###

##### 1. 思路：动态规划 #####

1.  状态转移方程：dp\[n\] = dp\[n-1\] + dp\[n-2\]
    
    > 从终点开始考虑。
    > 
    >  *  青蛙最后一次跳1步的情况：情况数 = 有 n-1 阶台阶的情况
    >  *  青蛙最后一次跳2步的情况：情况数 = 有 n-2 阶台阶的情况
2.  dp\[0\] = 1, dp\[1\] = 1

##### 2. 时间复杂度：O(n) #####

##### 3. 空间复杂度：O(1) #####

##### 4. 实现 #####

/** * @param {number} n * @return {number} */
    var numWays = function(n) { 
        // 预处理（无）
    
        // 动态规划
        let dp0 = 1, dp1 = 1;
        if(n <= 1) return 1;
    
        while(n > 1){ 
            let temp = dp0;
            dp0 = dp1;
            dp1 = (temp + dp0) % (1e9+7);	// 结果取模 1e9+7
            n--;
        }
    
        return dp1;
    };

[Offer 10 _easy]: https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70]: /images/20221120/90e9bfae39984e3cb865d418b2567d70.png

发表评论取消回复

表情：

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

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

相关阅读

相关青蛙跳台阶问题

> [剑指 Offer 10 \[easy\]][Offer 10 _easy] > ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGV

电玩女神/ 2022年12月27日 01:48/ 0 赞/ 152 阅读

相关青蛙跳台阶问题

一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法。在数量很小的情况下我们很简单的就知道问题的解如台阶为1 f(1

约定不等于承诺〃/ 2022年12月11日 03:23/ 0 赞/ 212 阅读

相关青蛙跳台阶问题

假设一只青蛙每次可以跳1步或2步，台阶总共有n步，总共有多少种跳法? public class StepAlgorithm {

た入场券/ 2022年10月14日 10:51/ 0 赞/ 155 阅读

相关青蛙跳台阶

题目描述(1) 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。题目描述(2) 一只青蛙一次可以跳上1级台阶，也可以跳

川长思鸟来/ 2022年05月26日 09:46/ 0 赞/ 194 阅读

相关青蛙跳台阶

青蛙跳台阶一只青蛙可以一次跳1层台阶，也可以一次跳2层台阶，问青蛙跳上n层台阶有多少种跳法？ > 思路：首先，考虑特殊情况： > > 当n等于0的时候，0层台

小咪咪/ 2022年05月19日 01:54/ 0 赞/ 179 阅读

相关变态青蛙跳台阶问题

青蛙跳台阶问题是一道很经典的问题：（1）一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法。（2）一只青蛙一次可以跳上

﹏ヽ暗。殇╰゛Y/ 2022年05月18日 01:28/ 0 赞/ 200 阅读

相关青蛙变态跳台阶问题

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。分析：因为n级台阶，第一步有n种跳法：跳1级、

Dear 丶/ 2022年05月15日 12:50/ 0 赞/ 200 阅读

相关青蛙跳台阶问题

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。首先我们考虑最简单的情况。如果只有1级

ゞ浴缸里的玫瑰/ 2022年05月15日 12:34/ 0 赞/ 202 阅读

相关动态青蛙跳台阶

运用动态规划的方法求青蛙跳台阶的问题 \\题目：\\一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法

矫情吗；*/ 2022年01月31日 16:04/ 0 赞/ 198 阅读

相关青蛙跳台阶算法

一、问题描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共需要多少种跳法。思路：首先考虑n等于0、1、2时的特殊情况，f(0) = 0

Bertha 。/ 2021年12月12日 02:31/ 0 赞/ 226 阅读