JZ69 跳臺階
描述
一只青蛙一次可以跳上1級臺階，也可以跳上2級，求該青蛙跳上一個 n 級的臺階總共有多少種跳法（先后次序不同算不同的結果），
資料范圍：1 \leq n \leq 401≤n≤40
要求：時間復雜度：O(n)O(n) ，空間復雜度： O(1)O(1)
方法1 遞回
思路
題目分析，假設f[i]表示在第i個臺階上可能的方法數，
逆向思維，如果我從第n個臺階進行下臺階，下一步有2中可能，一種走到第n-1個臺階，一種是走到第n-2個臺階，
所以f[n] = f[n-1] + f[n-2]，那么初始條件了，f[0] = f[1] = 1，
所以就變成了：f[n] = f[n-1] + f[n-2], 初始值f[0]=1, f[1]=1
代碼
if(target == 0 || target == 1) return 1;
return jumpFloor(target - 1) + jumpFloor(target - 2);
方法2 遞回改進
思路
f(2)計算了兩次，f(1)計算了3次，f(0)計算了2次，可以采用一個陣列存盤已經被計算過的值
此方法編譯不通過，空間復雜度過高
代碼
int[] f = new int[50];
if (target <= 1) return 1;
if (f[target] != 0) return f[target];
return f[target] = (jumpFloor(target - 1) + jumpFloor(target - 2));
方法3 動態規劃
思路
思路：既然與斐波那契數列相同，我們就把它放入陣列中來解決，
具體做法：
step 1：創建一個長度為n+1的陣列，因為只有n+1才能有下標第n項，我們用它記錄前n項斐波那契數列，
step 2：根據公式，初始化第0項和第1項，
step 3：遍歷陣列，依照公式某一項等于前兩項之和，將陣列后續元素補齊，即可得到fib[n]fib[n]fib[n]
代碼
package esay.JZ69跳臺階;
public class Solution {
public static int jumpFloor(int target) {
//方法1
/*if(target == 0 || target == 1) return 1;
return jumpFloor(target - 1) + jumpFloor(target - 2);*/
//方法2
/*int[] f = new int[50];
if (target <= 1) return 1;
if (f[target] != 0) return f[target];
return f[target] = (jumpFloor(target - 1) + jumpFloor(target - 2));*/
//方法3
if (target <= 1)
return 1;
int[] temp = new int[target + 1];
//初始化
temp[0] = 1;
temp[1] = 1;
//遍歷相加
for (int i = 2; i <= target; i++)
temp[i] = temp[i - 1] + temp[i - 2];
return temp[target];
}
public static void main(String[] args) {
System.out.println(jumpFloor(37));
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/535965.html
標籤：Java
上一篇：開發者工具｜15款音視頻開發者必備實用工具，看看你用過幾個？
下一篇：資料庫平滑擴容方案剖析