溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
一只青蛙一次可以跳上 1 級臺階，也可以跳上2 級。求該青蛙跳上一個n 級的臺階總共有多少種跳法
假設(shè)，一級臺階，有f(1)種方法，二級有f(2)種，以此類推，n級有f(n)種方法。
可以看出，f(1)=1;f(2)=2。
那么，假設(shè)n級臺階，那么第一步就有兩種情況，跳一步，跟跳兩步。
情況一：跳一步，那么接下去的就是f(n-1)；
情況二：跳兩步，那么接下去的就是f(n-2)。
所以總數(shù)是f(n)=f(n-1)+f(n-2)。
public int cal(int n){
if(n<=0){
return -1;
}
if(n==1||n==2){
return n;
}
else{
return cal(n-1)+cal(n-2);
}
}假設(shè)f(n)是n個臺階跳的次數(shù)。
f(1) = 1
f(2) 會有兩個跳得方式，一次1階或者2階，這回歸到了問題f(1),f(2) = f(2-1) + f(2-2)
f(3) 會有三種跳得方式，1階、2階、3階，那么就是第一次跳出1階后面剩下：f(3-1);第一次跳出2階，剩下f(3-2)；第一次3階，那么剩下f(3-3).因此結(jié)論是
f(3) = f(3-1)+f(3-2)+f(3-3)
f(n)時，會有n中跳的方式，1階、2階...n階，得出結(jié)論：
f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + f(n-n) => f(0) + f(1) + f(2) + f(3) + ... + f(n-1) == f(n) = 2*f(n-1)
public long jumpFloor(int n) {
if (n <= 0)
return -1;
if (n == 1)
return 1;
return 2 * jumpFloor(n - 1);
}考慮到效率，也可以改成迭代來做。
免責聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機網(wǎng)站二維碼