leetcode--青蛙跳台阶(斐波那契、动态规划)

阳光穿透心脏的1/2处 2023-02-14 15:52 10阅读 0赞

## 题目描述 ##

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

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

## 动态规划 ##

动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题的解将由上一个子问题的解推出。

## 解决方法 ##

递归超时，考察`动态规划`  
1.时间复杂度O(n)，空间复杂度O(1)的动态规划

class Solution {
        
        public int numWays(int n) {
        
            if(n<0){
        
                return 0;
            }
            if(n==0 || n==1){
        
                return 1;
            }
            if(n==2){
        
                return 2;
            }
            int a=1,b=2,temp=0;
            for(int i=3;i<=n;i++){
        
                temp=(a+b)%1000000007;
                a=b;
                b=temp;
            }
            return temp;
    
        }
    }

2.时间复杂度O(n)，空间复杂度O(n)的动态规划

class Solution {
        
        public int numWays(int n) {
        
            if(n<0){
        
                return 0;
            }
            if(n==0 || n==1){
        
                return 1;
            }
            
            int[] a= new int[n+1];
            a[1]=1;
            a[2]=2;
            for(int i=3;i<=n;i++){
        
                a[i]=(a[i-1]+a[i-2])%1000000007;
            }
            return a[n];
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 leetcode--青蛙跳台阶(斐波那契、动态规划)

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

阳光穿透心脏的1/2处/ 2023年02月14日 15:52/ 0 赞/ 11 阅读

相关 java青蛙跳台阶,斐波那契和青蛙跳台阶问题（Java）

/\\ \ 现在要求输入一个整数n，请你输出斐波那契数列的第n项。 \ @param args \/ public int Fibonacci(int n) \{ i

客官°小女子只卖身不卖艺/ 2023年01月13日 10:23/ 0 赞/ 164 阅读

相关 Leetcode 题解 - 动态规划-斐波那契数列

Leetcode 题解 - 动态规划文章目录 Leetcode 题解 - 动态规划斐波那契数列系列 509. 斐波那契数（

- 日理万妓/ 2023年01月13日 04:21/ 0 赞/ 165 阅读

相关斐波那契数列 - 动态规划

斐波那契数列写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下： F(0) = 0, F(1) = 1 F(N) =

妖狐艹你老母/ 2022年12月16日 13:05/ 0 赞/ 186 阅读

相关青蛙跳台阶 - 动态规划

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

雨点打透心脏的1/2处/ 2022年11月22日 12:53/ 0 赞/ 188 阅读

相关 JavaScript实现青蛙跳台阶问题（斐波那契数列）

问题一：一只青蛙一次可以跳上一阶台阶，也可以跳上二阶台阶，请这只可怜的青蛙跳上N阶台阶有几种方法？分析：当N=1时有一种跳法，当N=2时有两种跳法，当N=3时有三种跳法，当

红太狼/ 2022年05月24日 07:26/ 0 赞/ 195 阅读

相关跳台阶 -- “斐波那契数列” java

跳台阶 – “斐波那契数列” java 题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）

痛定思痛。/ 2022年05月08日 02:40/ 0 赞/ 148 阅读

相关斐波那契数列和青蛙跳台阶

public class Fibonacci { / 简单的递归，效率较低，因为有很多数字重复计算了

た入场券/ 2022年04月24日 15:20/ 0 赞/ 165 阅读

相关动态规划斐波那契

运用动态规划描述斐波那契数列，运用动态规划使得问题简化，运算速度大幅提升。 private static int fib(int n) { if(n==

淩亂°似流年/ 2022年02月02日 11:15/ 0 赞/ 245 阅读

相关剑指offfer-斐波那契数列青蛙跳台阶矩阵覆盖

斐波那契数列 f(0)=0 f(1)=1 f(n)=f(n-1)+f(n-2) 这种大问题拆分小问题的求解方式，且子问题内容相同，一定可以用递归若不允许递归

墨蓝/ 2021年11月11日 19:20/ 0 赞/ 236 阅读