1.題目

描述

一隻青蛙一次可以跳上1級台階，也可以跳上2級。求該青蛙跳上一個 n 級的台階總共有多少種跳法（先後次序不同算不同的結果）。

數據範圍：1 ≤n≤40

要求：時間複雜度：O(n) ，空間複雜度： O(1)

示例1

輸入：

2

返回值：

2

説明：

青蛙要跳上兩級台階有兩種跳法，分別是：先跳一級，再跳一級或者直接跳兩級。因此答案為2

示例2

輸入：

7

返回值：

21

2. 題解思路

本題的關鍵是套用動態規劃的模板，對問題進行拆解。

具體思路是：

如果文字描述的不太清楚，你可以參考視頻的詳細講解：B站@好易學數據結構

3.編碼實現

核心代碼：

func jumpFloor(number int) int {
    if number == 1 {
        return 1
    }
    //1.定義狀態.   i:第i個台階； dp[i]:跳到第i個台階的跳法
    dp := make([]int, number+1)
    //2.初始化邊界條件：    dp[1]=1，即第一個台階只有1種跳法；dp[2]=2，即第二個台階有2種跳法；
    dp[1] = 1
    dp[2] = 2
    //3.確定遞推公式： dp[i]=dp[i-1]+dp[i-2]
    for i := 3; i <= number; i++ {
        //到第i個台階有2種方法：從第 i-1跳上來，或者從第 i-2跳上來
        dp[i] = dp[i-1] + dp[i-2]
    }
    //4.輸出結果
    return dp[number]
}

具體完整代碼你可以參考下面視頻的詳細講解。

• Python編碼：B站@好易學數據結構
• Java編碼：B站@好易學數據結構
• Golang編碼：B站@好易學數據結構

4.總結

本題是動態規劃的經典題目，重點在於理解動態規劃的解題思路。對於第i個台階，只能從i-1或者i-2個台階跳上來，因此遞推公式是：dp[i] = dp[i - 1] + dp[i - 2]。

《數據結構與算法》深度精講課程正式上線啦！7 大核心算法模塊全解析：

  ✅   鏈表

  ✅   二叉樹

  ✅   二分查找、排序

  ✅   堆、棧、隊列

  ✅   回溯算法

  ✅   哈希算法

  ✅   動態規劃

無論你是備戰筆試面試、提升代碼效率，還是突破技術瓶頸，這套課程都將為你構建紮實的算法思維底座。🔥立即加入學習打卡，與千名開發者共同進階！

• Python編碼實現：B站@好易學數據結構
• Java編碼實現：B站@好易學數據結構
• Golang編碼實現：B站@好易學數據結構

對於LeetCode數據結構與算法，我們總結了一套【可視化+圖解】方法，依據此方法來解決相關問題，算法變得易於理解，寫出來的代碼可讀性高也不容易出錯。具體也可以參考視頻詳細講解。

今日佳句：燕趙多佳人，美者顏如玉。