leetcode怎么解決青蛙跳臺階問題

本篇內容介紹了“l(fā)eetcode怎么解決青蛙跳臺階問題”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

一只青蛙一次可以跳上1級臺階，也可以跳上2級臺階。求該青蛙跳上一個 n 級的臺階總共有多少種跳法。

答案需要取模 1e9+7（1000000007），如計算初始結果為：1000000008，請返回 1。

示例 1：

輸入：n = 2

輸出：2

示例 2：

輸入：n = 7

輸出：21

提示：

0 <= n <= 100

解題思路

設跳上 nn 級臺階有 f(n)f(n) 種跳法。在所有跳法中，青蛙的最后一步只有兩種情況：跳上 11 級或 22 級臺階。

當為 11 級臺階：剩 n-1n?1 個臺階，此情況共有 f(n-1)f(n?1) 種跳法；

當為 22 級臺階：剩 n-2n?2 個臺階，此情況共有 f(n-2)f(n?2) 種跳法。

f(n)f(n) 為以上兩種情況之和，即 f(n)=f(n-1)+f(n-2)f(n)=f(n?1)+f(n?2) ，以上遞推性質為斐波那契數(shù)列。本題可轉化為 求斐波那契數(shù)列第 nn 項的值 ，與 面試題10- I. 斐波那契數(shù)列 等價，唯一的不同在于起始數(shù)字不同。

青蛙跳臺階問題：f(0)=1f(0)=1 , f(1)=1f(1)=1 , f(2)=2f(2)=2 ；

斐波那契數(shù)列問題：f(0)=0f(0)=0 , f(1)=1f(1)=1 , f(2)=1f(2)=1 。

斐波那契數(shù)列的定義是 f(n + 1) = f(n) + f(n - 1)f(n+1)=f(n)+f(n?1) ，生成第 nn 項的做法有以下幾種：

遞歸法：

原理：把 f(n)f(n) 問題的計算拆分成 f(n-1)f(n?1) 和 f(n-2)f(n?2) 兩個子問題的計算，并遞歸，以 f(0)f(0) 和 f(1)f(1) 為終止條件。

缺點：大量重復的遞歸計算，例如 f(n)f(n) 和 f(n - 1)f(n?1) 兩者向下遞歸都需要計算 f(n - 2)f(n?2) 的值。

記憶化遞歸法：

原理：在遞歸法的基礎上，新建一個長度為 nn 的數(shù)組，用于在遞歸時存儲 f(0)f(0) 至 f(n)f(n) 的數(shù)字值，重復遇到某數(shù)字時則直接從數(shù)組取用，避免了重復的遞歸計算。

缺點：記憶化存儲的數(shù)組需要使用 O(N)O(N) 的額外空間。

動態(tài)規(guī)劃：

原理：以斐波那契數(shù)列性質 f(n + 1) = f(n) + f(n - 1)f(n+1)=f(n)+f(n?1) 為轉移方程。

從計算效率、空間復雜度上看，動態(tài)規(guī)劃是本題的最佳解法。

動態(tài)規(guī)劃解析：

狀態(tài)定義：設 dpdp 為一維數(shù)組，其中 dp[i]dp[i] 的值代表 斐波那契數(shù)列第 $i$ 個數(shù)字 。

轉移方程：dp[i + 1] = dp[i] + dp[i - 1]dp[i+1]=dp[i]+dp[i?1] ，即對應數(shù)列定義 f(n + 1) = f(n) + f(n - 1)f(n+1)=f(n)+f(n?1) ；

初始狀態(tài)：dp[0] = 1dp[0]=1, dp[1] = 1dp[1]=1 ，即初始化前兩個數(shù)字；

返回值：dp[n]dp[n] ，即斐波那契數(shù)列的第 nn 個數(shù)字。

空間復雜度優(yōu)化：

若新建長度為 nn 的 dpdp 列表，則空間復雜度為 O(N)O(N) 。

由于 dpdp 列表第 ii 項只與第 i-1i?1 和第 i-2i?2 項有關，因此只需要初始化三個整形變量 sum, a, b ，利用輔助變量 sumsum 使 a, ba,b 兩數(shù)字交替前進即可 （具體實現(xiàn)見代碼） 。

因為節(jié)省了 dpdp 列表空間，因此空間復雜度降至 O(1)O(1) 。

循環(huán)求余法：

大數(shù)越界：隨著 nn 增大, f(n)f(n) 會超過 Int32 甚至 Int64 的取值范圍，導致最終的返回值錯誤。

求余運算規(guī)則：設正整數(shù) x, y, px,y,p ，求余符號為 \odot⊙ ，則有 (x + y) \odot p = (x \odot p + y \odot p) \odot p(x+y)⊙p=(x⊙p+y⊙p)⊙p 。

解析：根據(jù)以上規(guī)則，可推出 f(n) \odot p = [f(n-1) \odot p + f(n-2) \odot p] \odot pf(n)⊙p=[f(n?1)⊙p+f(n?2)⊙p]⊙p ，從而可以在循環(huán)過程中每次計算 sum = a + b \odot 1000000007sum=a+b⊙1000000007 ，此操作與最終返回前取余等價

代碼實現(xiàn)

func numWays(n int) int {   if n==0{       return 1   }   if n<=2{       return n   }
   a:=make([]int,n)   a[0]=1   a[1]=2   c:=1000000007   for i:=2;i<n;i++{       a[i]=(a[i-1]+a[i-2])%c   }   return a[n-1]}

“l(fā)eetcode怎么解決青蛙跳臺階問題”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關的知識可以關注億速云網(wǎng)站，小編將為大家輸出更多高質量的實用文章！