剑指 Offer 10- II. 青蛙跳台阶问题

╰+哭是因爲堅強的太久メ 2022-10-16 14:21 124阅读 0赞

#### 题目描述 ####

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

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

#### 示例 1： ####

> 输入：n = 2  
> 输出：2

#### 示例 2： ####

> 输入：n = 7  
> 输出：21

#### 示例 3： ####

> 输入：n = 0  
> 输出：1

#### 提示： ####

> 0 <= n <= 100

#### 思路分析 ####

这题与斐波那契数列基本相同。考虑3阶爬法与2阶爬法之间的关系，即3阶爬法=（2阶爬法再跳一次一阶）+（1阶爬法再跳一次二阶）+

1.  递归法(超时)

int numWays(int n) {
        
    	if(n==1 ||n==0 )
    	{
        
    		return 1;
    	}
    	if(n==2)
    	{
        
    		return 2;
    	}
    	return numWays(n-1)+numWays(n-2);
    }

1.  动态规划

状态转移方程基于斐波那契数列的特性，即为：dp\[i\]=(dp\[i-1\]+dp\[i-2\])

class Solution {
        
    public:
        int numWays(int n)
        {
        
            if(n==0 )
            {
        
                return 1;
            }
            // 到第i层可能的解法数目 
            int dp[1000];
            // base case
            dp[0]=1;
            dp[1]=1;
            dp[2]=2;
            for(int i=2;i<=n;i++)
            {
        
                dp[i]=(dp[i-1]+dp[i-2])%1000000007;
            }
            return dp[n];
    
        }
    };

#### 总结 ####

斐波那契数列之所以慢，是因为递归本身就存在重复计算问题，打DP表则可以很好的解决这个问题。

发表评论取消回复

表情：

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

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

相关阅读

相关剑指Offer10-II_青蛙跳台阶问题

剑指 Offer 10- II. 青蛙跳台阶问题题目：青蛙跳台阶问题 LeetCode地址：[剑指 Offer 10- II. 青蛙跳台阶问题][Offer

快来打我*/ 2023年10月05日 13:12/ 0 赞/ 39 阅读

相关【剑指 Offer 10- II. 青蛙跳台阶问题】

package com.example.demomain.demoleetcode.easy; import org.junit.Test;

￡神魔★判官ぃ/ 2023年09月26日 16:29/ 0 赞/ 3 阅读

相关剑指 Offer 10- II. 青蛙跳台阶问题

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

超、凢脫俗/ 2023年02月23日 05:08/ 0 赞/ 16 阅读

相关剑指 Offer 10- II. 青蛙跳台阶问题

题目一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。答案需要取模 1e9+7（1000000007），如计算初始结

布满荆棘的人生/ 2022年12月16日 13:28/ 0 赞/ 121 阅读

相关剑指 Offer 10- II. 青蛙跳台阶问题

题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。答案需要取模 1e9+7（1000000007），如计算初始结果

Love The Way You Lie/ 2022年12月07日 12:17/ 0 赞/ 120 阅读

相关 LeetCode 剑指 Offer 10- II. 青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。答案需要取模 1e9+7（1000000007），如计算初始结果为：100

喜欢ヅ旅行/ 2022年11月09日 14:27/ 0 赞/ 115 阅读

相关剑指 Offer 10- II. 青蛙跳台阶问题

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。答案需要取模 1e9+7（1000000007），如计算初

╰+哭是因爲堅強的太久メ/ 2022年10月16日 14:21/ 0 赞/ 125 阅读

相关【leetcode】剑指 Offer 10- II. 青蛙跳台阶问题

剑指 Offer 10- II. 青蛙跳台阶问题题目难度：简单方法一：动态规划 > 链接：[https://leetcode-cn.com/proble

Love The Way You Lie/ 2022年10月16日 09:51/ 0 赞/ 146 阅读

相关剑指 Offer 10- II. 青蛙跳台阶问题

链接：[https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/][https_leetcode-c

缺乏、安全感/ 2022年10月07日 15:50/ 0 赞/ 143 阅读

相关剑指 Offer 10- II. 青蛙跳台阶问题

[力扣![icon-default.png?t=L892][icon-default.png_t_L892]/images/20220828/76d17be094cb42ca8

心已赠人/ 2022年09月11日 13:18/ 0 赞/ 140 阅读