問題
- 一只青蛙一次可以跳上1級臺階，也可以跳上2級臺階，求該青蛙跳上一個 n 級的臺階總共有多少種跳法，
答案需要取模 1e9+7（1000000007），如計算初始結果為：1000000008，請回傳 1，
解決
class Solution {
static int MOD=1000000007;
public int numWays(int n) {
// **3.動態規劃**：窮舉可以發現f(n)=f(n-1)+f(n-2);確定邊界：f(0)=1,f(1)=1,f(2)=2;最佳解f(n)=f(n-1)+f(n-2);得到最終解決方案(邊界+最優解)
if(n==0) return 1;
if(n<=2) return n;
int a=1,b=1,c=2;
for(int i=3;i<=n;i++){ //可以近似看作一個不斷移動的陣列，后面一個值等于前兩個相加
b=a;
a=c;
c=(a+b)%MOD;
}
return c;
}
}
// 青蛙跳臺階：
// 遞回、帶備忘錄的遞回、動態規劃
// **1.遞回**
// public int numWays(int n) {
// if(n==1) return 1;
// if(n==2) return 2;
// return numWays(n-1)+numWays(n-2);
// }
//**2. 帶備忘的遞回（減少了遞回程序中的重復操作）**
// static int MOD=1000000007;
// HashMap<Integer,Integer> map=new HashMap(); //定義hashmap應該放在方法外面，在不方法每次呼叫都會創一個新的hashmap
// public int numWays(int n) {
// if(n==0) return 1;
// if(n<=2) return n;
// if(map.containsKey(n)) //檢查 hashMap 中是否存在指定的 key 對應的映射關系，
// {
// return map.get(n); //如果備忘里存在就直接回傳，
// }else{
// map.put(n,(numWays(n-1)+numWays(n-2))%MOD);
// return map.get(n);
// }
// // return numWays(n-1)+numWays(n-2);
// }
總結
- 時間復雜度分析:(1.遞回)-O(n^2)---(2.帶備忘的遞回)-O(n)---(3.動態規劃)-O(n)
- 不管是遞回還是帶備忘錄的遞回都是至上而下的,而動態規劃是至下而上;
- 遞回有大量的重復操作,而帶備忘錄的遞回和動態規劃每次操作都只執行一次,從而大大節省了時間
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/498636.html
標籤：其他