leetcode怎么解決青蛙跳臺(tái)階問題
本篇內(nèi)容介紹了“l(fā)eetcode怎么解決青蛙跳臺(tái)階問題”的有關(guān)知識(shí)，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！
成都創(chuàng)新互聯(lián)專注于文山州網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗(yàn)。 熱誠為您提供文山州營銷型網(wǎng)站建設(shè)，文山州網(wǎng)站制作、文山州網(wǎng)頁設(shè)計(jì)、文山州網(wǎng)站官網(wǎng)定制、微信小程序開發(fā)服務(wù)，打造文山州網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供文山州網(wǎng)站排名全網(wǎng)營銷落地服務(wù)。
一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)臺(tái)階。求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法。
答案需要取模 1e9+7（1000000007），如計(jì)算初始結(jié)果為：1000000008，請返回 1。
示例 1：
輸入：n = 2
輸出：2
示例 2：
輸入：n = 7
輸出：21
提示：
0 <= n <= 100
解題思路
設(shè)跳上 nn 級(jí)臺(tái)階有 f(n)f(n) 種跳法。在所有跳法中，青蛙的最后一步只有兩種情況：跳上 11 級(jí)或 22 級(jí)臺(tái)階。
當(dāng)為 11 級(jí)臺(tái)階：剩 n-1n?1 個(gè)臺(tái)階，此情況共有 f(n-1)f(n?1) 種跳法；
當(dāng)為 22 級(jí)臺(tái)階：剩 n-2n?2 個(gè)臺(tái)階，此情況共有 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) ，以上遞推性質(zhì)為斐波那契數(shù)列。本題可轉(zhuǎn)化為 求斐波那契數(shù)列第 nn 項(xiàng)的值 ，與 面試題10- I. 斐波那契數(shù)列 等價(jià)，唯一的不同在于起始數(shù)字不同。
青蛙跳臺(tái)階問題：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 項(xiàng)的做法有以下幾種：
遞歸法：
原理：把 f(n)f(n) 問題的計(jì)算拆分成 f(n-1)f(n?1) 和 f(n-2)f(n?2) 兩個(gè)子問題的計(jì)算，并遞歸，以 f(0)f(0) 和 f(1)f(1) 為終止條件。
缺點(diǎn)：大量重復(fù)的遞歸計(jì)算，例如 f(n)f(n) 和 f(n - 1)f(n?1) 兩者向下遞歸都需要計(jì)算 f(n - 2)f(n?2) 的值。
記憶化遞歸法：
原理：在遞歸法的基礎(chǔ)上，新建一個(gè)長度為 nn 的數(shù)組，用于在遞歸時(shí)存儲(chǔ) f(0)f(0) 至 f(n)f(n) 的數(shù)字值，重復(fù)遇到某數(shù)字時(shí)則直接從數(shù)組取用，避免了重復(fù)的遞歸計(jì)算。
缺點(diǎn)：記憶化存儲(chǔ)的數(shù)組需要使用 O(N)O(N) 的額外空間。
動(dòng)態(tài)規(guī)劃：
原理：以斐波那契數(shù)列性質(zhì) f(n + 1) = f(n) + f(n - 1)f(n+1)=f(n)+f(n?1) 為轉(zhuǎn)移方程。
從計(jì)算效率、空間復(fù)雜度上看，動(dòng)態(tài)規(guī)劃是本題的最佳解法。
動(dòng)態(tài)規(guī)劃解析：
狀態(tài)定義：設(shè) dpdp 為一維數(shù)組，其中 dp[i]dp[i] 的值代表 斐波那契數(shù)列第 $i$ 個(gè)數(shù)字 。
轉(zhuǎn)移方程：dp[i + 1] = dp[i] + dp[i - 1]dp[i+1]=dp[i]+dp[i?1] ，即對(duì)應(yīng)數(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 ，即初始化前兩個(gè)數(shù)字；
返回值：dp[n]dp[n] ，即斐波那契數(shù)列的第 nn 個(gè)數(shù)字。
空間復(fù)雜度優(yōu)化：
若新建長度為 nn 的 dpdp 列表，則空間復(fù)雜度為 O(N)O(N) 。
由于 dpdp 列表第 ii 項(xiàng)只與第 i-1i?1 和第 i-2i?2 項(xiàng)有關(guān)，因此只需要初始化三個(gè)整形變量 sum, a, b ，利用輔助變量 sumsum 使 a, ba,b 兩數(shù)字交替前進(jìn)即可 （具體實(shí)現(xiàn)見代碼） 。
因?yàn)楣?jié)省了 dpdp 列表空間，因此空間復(fù)雜度降至 O(1)O(1) 。
循環(huán)求余法：
大數(shù)越界：隨著 nn 增大, f(n)f(n) 會(huì)超過 Int32 甚至 Int64 的取值范圍，導(dǎo)致最終的返回值錯(cuò)誤。
求余運(yùn)算規(guī)則：設(shè)正整數(shù) x, y, px,y,p ，求余符號(hào)為 \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)過程中每次計(jì)算 sum = a + b \odot 1000000007sum=a+b⊙1000000007 ，此操作與最終返回前取余等價(jià)
代碼實(shí)現(xiàn)
func numWays(n int) int {if n==0{return 1}if n<=2{return n}a:=make([]int,n)a[0]=1a[1]=2c:=1000000007for i:=2;i<n;i++{a[i]=(a[i-1]+a[i-2])%c}return a[n-1]}
“l(fā)eetcode怎么解決青蛙跳臺(tái)階問題”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！
當(dāng)前題目：leetcode怎么解決青蛙跳臺(tái)階問題
本文鏈接：http://muchs.cn/article14/gppjge.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供建站公司、品牌網(wǎng)站制作、外貿(mào)建站、App設(shè)計(jì)、虛擬主機(jī)、網(wǎng)站設(shè)計(jì)公司
聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)
