一只青蛙一次可以跳上 1 級臺階,也可以跳上2 級。求該青蛙跳上一個n 級的臺階總共有多少種跳法
假設,一級臺階,有f(1)種方法,二級有f(2)種,以此類推,n級有f(n)種方法。
可以看出,f(1)=1;f(2)=2。
那么,假設n級臺階,那么第一步就有兩種情況,跳一步,跟跳兩步。
情況一:跳一步,那么接下去的就是f(n-1);
情況二:跳兩步,那么接下去的就是f(n-2)。
所以總數是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); } }
假設f(n)是n個臺階跳的次數。
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).因此結論是
f(3) = f(3-1)+f(3-2)+f(3-3)
f(n)時,會有n中跳的方式,1階、2階...n階,得出結論:
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); }
考慮到效率,也可以改成迭代來做。
免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。