入口

力扣https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/

題目描述

一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)臺(tái)階。求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法。

答案需要取模 1e9+7（1000000007），如計(jì)算初始結(jié)果為：1000000008，請(qǐng)返回 1。

示例 1：

        輸入：n = 2
        輸出：2
示例 2：

        輸入：n = 7
        輸出：21
示例 3：

        輸入：n = 0
        輸出：1
提示：

        0 <= n <= 100

斐波那契數(shù)列 

青蛙跳臺(tái)階問(wèn)題是一種經(jīng)典的動(dòng)態(tài)規(guī)劃問(wèn)題，可以通過(guò)類比斐波那契數(shù)列來(lái)求解。問(wèn)題的關(guān)鍵在于理解青蛙跳躍的可能路徑：

• 第1級(jí)臺(tái)階：只有 1 種方法，即青蛙直接跳1級(jí)到達(dá)目標(biāo)。

• 第2級(jí)臺(tái)階：有 2 種方法：

  1. 跳1級(jí)，然后再跳1級(jí)：青蛙可以選擇先跳到第1級(jí)臺(tái)階，然后再跳1級(jí)到第2級(jí)。
  2. 直接跳2級(jí)：青蛙可以選擇直接從地面跳到第2級(jí)。

• 第n級(jí)臺(tái)階（n > 2）：對(duì)于任意第n級(jí)臺(tái)階，青蛙有兩種可能的最后一步：

  1. 從第(n-1)級(jí)臺(tái)階跳1級(jí)：青蛙可以先跳到第(n-1)級(jí)臺(tái)階，然后再跳1級(jí)到達(dá)第n級(jí)。
  2. 從第(n-2)級(jí)臺(tái)階跳2級(jí)：青蛙可以先跳到第(n-2)級(jí)臺(tái)階，然后直接跳2級(jí)到達(dá)第n級(jí)。

這個(gè)思路的核心在于，每個(gè)臺(tái)階的到達(dá)方法數(shù)是基于前兩個(gè)臺(tái)階的方法數(shù)之和，因?yàn)榍嗤芸梢赃x擇跳1級(jí)或者2級(jí)。

遞推公式：F(n) = F(n-1) + F(n-2)

方法一：遞歸

 Java示例

class Solution {
    public int climbStairs(int n) {
        if(n==1 || n==2){
            return n;
        }
        return climbStairs(n-1) + climbStairs(n-2);
    }
}

時(shí)間復(fù)雜度：O(2^n)

空間復(fù)雜度：O(n)

方法二：記憶遞歸

方法一缺點(diǎn)： 多了很多重復(fù)計(jì)算(如紅框圈出來(lái)的地方)，記憶遞歸的講每次計(jì)算結(jié)果存儲(chǔ)，不再重復(fù)計(jì)算。

方法一復(fù)雜度分析

 Java示例

class Solution {
    public int climbStairs(int n) {
        int memo[] = new int[n+1];//存儲(chǔ)計(jì)算結(jié)果
        return climb(memo,n);
    }
    public int climb(int[] memo,int n){
        if(n==1 || n==2){
            memo[n] = n;
        }
        if(memo[n] == 0){
            memo[n] = climb(memo,n-1) + climb(memo,n-2);
        }
        return memo[n];
    }
}

時(shí)間復(fù)雜度：O(n)

空間復(fù)雜度：O(n)

方法三：動(dòng)態(tài)規(guī)劃

Java示例

class Solution {
    public int climbStairs(int n) {
        if(n==1 || n==2){
           return n;
        }
        int dp[] = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        for(int i=3;i<=n;i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n-1] + dp[n-2];
    }
}

時(shí)間復(fù)雜度：O(n)

空間復(fù)雜度：O(n)

方法四：斐波那契數(shù)列

在方法一的dp數(shù)組中只有兩個(gè)元素被使用，現(xiàn)在將浪費(fèi)的空間優(yōu)化掉，將空間復(fù)雜度降為O(1)

Java示例

class Solution {
    public int climbStairs(int n) {
        if(n==1 || n==2){
           return n;
        }
        int first=1;
        int second = 2;
        for(int i=3;i<n;i++){
           int third = first + second;
           first = second;
           second = third;
        }
        return first + second;
    }
}

時(shí)間復(fù)雜度：O(n)

空間復(fù)雜度：O(1)