劍指 Offer 10- II. 青蛙跳臺階問題
一只青蛙一次可以跳上1級臺階，也可以跳上2級臺階，求該青蛙跳上一個 n 級的臺階總共有多少種跳法，
答案需要取模 1e9+7（1000000007），如計算初始結果為：1000000008，請回傳 1，
同斐波那契數列，注意初始值的不同！
方法一：遞回，超時
public static int numWays(int n){
if(n < 1) return 1;
if(n < 3) return n;
else return (numWays(n-2) + numWays(n-1))%1000000007;
}
方法二：迭代陣列
public static int numWaysTwo(int n){
int[] dp = new int[n+1];
//dp[0] = 1;
if(n <= 1)return 1;
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i <= n; i++){
dp[i] = dp[i-1] + dp[i-2];
dp[i] %=1000000007;
}
return dp[n];
}
方法三：map存取
public static int numWaysThree(int n){
HashMap<Integer,Integer> map = new HashMap<>();
if(n < 1) return 1;
if(n < 3) return n;
if(!map.containsKey(n)){
map.put(n,numWaysThree(n-1) + numWaysThree(n-2));
}
return map.get(n);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/112362.html
標籤：其他
上一篇：冒泡排序-java