如果某個遞歸，除了初始項之外，具有如下的形式
F(N) = C1 * F(N) + C2 * F(N-1) + … + Ck * F(N-k) ( C1…Ck 和k都是常數)
并且這個遞歸的表達式是嚴格的、不随條件轉移的
那麼都存在類似斐波那契數列的優化，時間複雜度都能優化成O(logN)
棋盤馬走日
遞歸：
public static int ways(int x, int y, int k) {
return f(x, y, k);
}
public static int f(int x, int y, int k) {
if(k == 0) {
return x==0 && y==0 ? 1 : 0;
}
if(x < 0 || x > 9 || y<0 || y>8) {
return 0;
}
return f(x+2, y-1, k-1)
+ f(x+2, y+1, k-1)
+ f(x+1, y+2,k-1)
+ f(x-1, y+2,k-1)
+ f(x- 2, y+1,k-1)
+ f(x - 2, y-1, k-1)
+ f(x-1, y-2,k-1)
+f(x + 1, y-2, k-1);
}
動态規劃：
public static int ways2(int x, int y, int k) {
int [][][] dp = new int[10][9][k+1];
dp[0][0][0] = 1;
for (int i = 1; i <= k; i++) {
for (int j = 0; j < 10; j++) {
for (int j2 = 0; j2 < 9; j2++) {
dp[j][j2][i] = getValue(dp, j+2, j2-1, i-1)
+ getValue(dp, j+2, j2+1, i-1)
+ getValue(dp, j+1, j2+2, i-1)
+ getValue(dp, j-1, j2+2, i-1)
+ getValue(dp, j-2, j2+1, i-1)
+ getValue(dp, j-2, j2-1, i-1)
+ getValue(dp, j-1, j2-2, i-1)
+ getValue(dp, j+1, j2-2, i-1)
;
}
}
}
return dp[x][y][k];
}
public static int getValue(int[][][] dp, int x, int y, int k) {
if(x < 0 || x > 9 || y<0 || y>8) {
return 0;
}
return dp[x][y][k];
}
劍指 Offer 10- I. 斐波那契數列
寫一個函數，輸入
n
，求斐波那契（Fibonacci）數列的第
n
項（即
F(N)
）。斐波那契數列的定義如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契數列由 0 和 1 開始，之後的斐波那契數就是由之前的兩數相加而得出。
答案需要取模 1e9+7（1000000007），如計算初始結果為：1000000008，請傳回 1。
示例 1：
輸入：n = 2
輸出：1
示例 2：
輸入：n = 5
輸出：5
提示：
-
0 <= n <= 100
方法一：遞歸（時間超限），通過優化可以AC
方法二：動态規劃
方法三：矩陣快速幂，遞推：
public int fib(int n) {
if(n==0)return 0;
if(n==1||n==2)return 1;
int[][]base={
{1,1},
{1,0}
};
int [][] res = matrixPower(base,n-1);
return res[0][0];
}
public int[][]matrixPower(int [][] m, int temp){
int[][] ret = {{1, 0}, {0, 1}};
while(temp!=0){
// 如果對應二進制位為1 則乘進去
if((temp&1)!=0){
ret = muliMatrix(ret, m);
}
m = muliMatrix(m, m);
temp>>=1;
}
return ret;
}
public static int[][] muliMatrix(int[][] a, int[][] b) {
int[][] c = new int[2][2];
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
c[i][j] = (int) (((long) a[i][0] * b[0][j] + (long) a[i][1] * b[1][j]) % 1000000007);
}
}
return c;
}
上樓問題
一個人可以一次往上邁1個台階，也可以邁2個台階
傳回這個人邁上N級台階的方法數
第n階可以從n-1階台階到達，也可以從n-2階台階到達：
F（n）= F（n-1）+ F（n-2）
若一個人一次可以上k步，p步，m步
求到N級台階
F（n）= f（n-k）+ f（n-p）+ f（n-m）
矩陣為 max（k，p，m） * max（k，p，m）
母牛問題
第一年農場有1隻成熟的母牛A，往後的每年：
1）每一隻成熟的母牛都會生一隻母牛
2）每一隻新出生的母牛都在出生的第三年成熟
3）每一隻母牛永遠不會死
傳回N年後牛的數量
n年的牛由n-1年牛的個數+n-3年牛個數（滿三年都生一隻小牛）
F（n）=F（n-1）+F（n-3）
字元問題
給定一個數N，想象隻由0和1兩種字元，組成的所有長度為N的字元串
如果某個字元串,任何0字元的左邊都有1緊挨着,認為這個字元串達标
傳回有多少達标的字元串
n位數，最左邊一位為1有：F（n-1）種方法；最左邊為0則倒數第二位必須為1，則有F（n-2）種方法
F（n）=F（n-1）+F（n-2）
每個人都有潛在的能量，隻是很容易被習慣所掩蓋，被時間所迷離，被惰性所消磨~