##題目描述 大家都知道斐波那契數列，現在要求輸入一個整數n，請你輸出斐波那契數列的第n項（從0開始，第0項為0）， n<=39
思路
-
遞回（函式堆疊呼叫消耗太高）
時間復雜度O(2^n)，空間復雜度O(n)， -
使用回圈替換遞回
時間復雜度O(n)，空間復雜度O(1)， -
動態規劃
時間復雜度O(n)，空間復雜度O(1)， -
矩陣快速冪
時間復雜度O(lgn)，空間復雜度O(1)，
遞回演算法
public class Solution {
public int Fibonacci(int n) {
if(n < 0) return 0;
if(n < 2) return n;
return Fibonacci(n-1)+Fibonacci(n-2);
}
}
回圈演算法
public class Solution {
public int Fibonacci(int n) {
int a = 0, b = 1, c = 1;
while(n-- > 0) {
a = b;
b = c;
c = a + b;
}
return a;
}
}
動態規劃
public class Solution {
public int Fibonacci(int n) {
int[] dp = new int[] {0, 1};
while(n-- > 0) {
dp[1] = dp[0] + dp[1];
dp[0] = dp[1] - dp[0];
}
return dp[0];
}
}
矩陣快速冪
class Solution {
private int[][] matmul(int[][] a, int[][] b, int m, int n, int t) {
int[][] tmp = new int[m][n];
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
tmp[i][j] = 0;
for(int k = 0; k < t; k++) {
tmp[i][j] += a[i][k] * b[k][j];
}
}
}
return tmp;
}
public int Fibonacci(int n){
if(n < 1) return 0;
if(n == 1) return 1;
int[][] matT = new int[][] {{1, 1}, {1, 0}};
int[][] fibT = new int[][] {{1}, {0}};
while(n > 1){
// 二進制轉換，最高位1用最終快速冪矩陣，其余位1用當前冪矩陣
if(n%2 == 1){
fibT = matmul(matT, fibT, 2, 1, 2);
}
matT = matmul(matT, matT, 2, 2, 2);
n /= 2;
}
fibT = matmul(matT, fibT, 2, 1, 2);
return fibT[1][0];
}
}
簡單快速冪求2的n次方
class Solution {
public long pow(int n) {
long ans = 1, base = 2;
while(n > 0) {
if(n%2 == 1) {
ans = (ans * base) % 1000000007;
}
base = (base * base) % 1000000007;
n >>= 1;
}
return ans;
}
}
筆記
1.快速冪余項的個數聯想二進制權重
2.回圈實作，三次賦值，一次加法
dp實作，兩次賦值，一次加法，一次減法
后者效率未見得高
3.尾遞回優化
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/88239.html
標籤：其他
上一篇：npf無法開啟