一只青蛙一次可以跳上一級臺階，也可以跳上兩級，求該青蛙跳上一個 n 級的臺階總共有多少種跳法（先后次序不同算不同的結果）
青蛙每次只有兩種跳法：一階或二階，假定第一次跳的是一階，那么剩下的是 n - 1 個臺階，總的跳法是 f(n - 1)
假定第一次跳的是二階，那么剩下的是 n - 2 個臺階，跳法是 f(n - 2)
通過實際情況可以得出：只有一階的時候 f(1) = 1 ,只有兩階的時候可以有 f(2) = 2
可以發現最終得出的是一個斐波那契數列：
public class Solution {
public int JumpFloor(int target) {
if(target <= 0) {
return 0;
}
if (target == 1 || target == 2) {
return target;
}
return JumpFloor(target - 1) + JumpFloor(target - 2);
}
}
遞回會影響效率，可以使用迭代
public int JumpFloor(int target) {
if(target == 1 || target == 2) {
return target;
}
// 第一階和第二階考慮過了，初始當前臺階為第三階，向后迭代
// 思路：當前臺階的跳法總數 = 當前臺階后退一階的臺階的跳法總數 + 當前臺階后退二階的臺階的跳法總數
// 當前臺階的跳法總數
int jumpSum = 0;
// 當前臺階后退一階的臺階的跳法總數（初始值當前臺階是第三階）
int jumpSumBackStep1 = 2;
// 當前臺階后退二階的臺階的跳法總數（初始值當前臺階是第三階）
int jumpSumBackStep2 = 1;
for(int i = 3; i <= target; i++) {
// 這一次迭代的跳法總數
jumpSum= jumpSumBackStep1 + jumpSumBackStep2;
// 下一次迭代后退兩階，相當于這一次迭代后退一階
jumpSumBackStep2 = jumpSumBackStep1;
// 下一次迭代后退一階，相當于這一次迭代跳法總數
jumpSumBackStep1 = jumpSum;
}
return jumpSum;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/127913.html
標籤：其他
上一篇：斐波那契數列