##題目描述 一只青蛙一次可以跳上1級臺階，也可以跳上2級，求該青蛙跳上一個n級的臺階總共有多少種跳法（先后次序不同算不同的結果），
思路
遞回重復子分支和函式堆疊呼叫影響效率，
計算前6項觀察規律：0：0，1：1，2:2，3:3，4:5，5:8
數列呈斐波那契數列規律，
最終解是由前面的解累積而成：
若樓梯階級 n = n
跳 2 步到 n：剩下的是第 n - 2 步沒跳，起始跳到第 n - 2 步設它為 pre2 種
跳 1 步到 n：剩下的是第 n - 1 步沒跳，起始跳到第 n - 1 步設它為 pre1 種
dp(i) = dp(i-2) + dp(i-1)
時間復雜度O(n)，空間復雜度O(1)，
遞回代碼
public class Solution {
public int JumpFloor(int target) {
if(target < 0) return 0;
if(target == 0) return 1;
return JumpFloor(target-1) + JumpFloor(target-2);
}
}
斐波那貧訓圈
public class Solution {
public int JumpFloor(int target) {
if(target < 3) return target;
int f1 = 1, f2 = 2, tmp = 0;
for(int i = 2; i < target; i++) {
tmp = f1 + f2;
f1 = f2;
f2 = tmp;
}
return f2;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/88248.html
標籤：其他
上一篇：POJ-2299 Ultra-QuickSort（用樹狀陣列求逆序對數）
下一篇：基于WIFI通信的