##題目描述 一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級，求該青蛙跳上一個n級的臺階總共有多少種跳法，
思路
斐波那契數列變種，
-
f(n)=f(n-1)+f(n-2)+……f(1)
f(n-1)=f(n-2)+……f(1)
兩式相減得f(n)=2f(n-1)
時間復雜度O(√n)，空間復雜度O(1)， -
動態規劃
f(n)=f(n-1)+f(n-2)+……f(1)
時間復雜度O(n2)，空間復雜度O(n)，
公式代碼
public class Solution {
public int JumpFloorII(int target) {
if(target < 3) return target;
int ans = 2;
for(int i = 2; i < target; i++) {
ans *= 2;
}
return ans;
}
}
dp代碼
import java.util.Arrays;
public class Solution {
public int JumpFloorII(int target) {
int[] dp = new int[target+1];
Arrays.fill(dp, 1);
dp[0] = 0;
for(int i = 2; i <= target; i++){
for(int j = 1; j < i; j++) {
dp[i] += dp[j];
}
}
return dp[target];
}
}
筆記
動規演算法用于理解一維的動態規劃，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/88250.html
標籤：其他
上一篇：基于WIFI通信的