一、斐波那契数列
斐波那契数列就是：当n=0时，F(n)=0；当n=1时，F(n)=1；当n>1时，F(n) = F(n-1)+F(n-2)。
根据斐波那契数列的定义，斐波那契数列为（从n=1开始）：1,1,2,3,5,8...，也就是除了第1项和第2项外，对于第N项，都有F(n) = F(n-1)+F(n-2)
1.时间复杂度为O(2n)的暴力递归算法
暴力递归算法是最慢的一种方法，加入要计算F(10)的值，那么就要计算F(9)和F(8)的值，而计算F(9)的值需要计算F(8)和F(7)的值，计算F(8)就需要计算F(7)和F(6)的值...这样就会造成多次的重复计算，例如F(8)和F(7)就要计算多次。递归算法虽然代码简单容易理解，但是效率低下，时间复杂度随n的值指数增长。
public int fib1(int n) { if (n < 1) return 0; if (n == 1 || n == 2) return 1; return fib1(n - 1) + fib1(n - 2); }
2.时间复杂度为O(n)的非递归算法
考虑到递归算法在每一步的计算中都重复地计算了很多不必要的值，因此问题就是如何避免计算那些重复的值。由于可以从左到右利用前面的两个值计算出每一项的值，然后通过顺序累加就可以求出第N项的值。
public int fib2(int n) { if (n < 1) return 0; if (n == 1 || n == 2) return 1; int first = 1; int second = 1; int tmp = 0; for (int i = 3; i <= n; i++) { tmp = second; second = first + second; first = tmp; } return second; }
3.时间复杂度为O(logn)的状态矩阵乘法算法
由于F(n) = F(n-1)+F(n-2)是二阶递推数列，而二阶递推数列一定可以用矩阵乘法的形式表示，且状态转移矩阵为2×2的矩阵。
(F(n), F(n-1)) = (F(n-1), F(n-2)) x {{a,b},{c,d}}（矩阵） 将F(1)=1,F(2)=1,F(3)=2,F(4)=3带入可以求出状态矩阵a=1,b=1,c=1,d=0(n-2)
(F(3),F(2))=(F(2),F(1)) × base
(F(4),F(3))=(F(3),F(2)) × base = (F(2),F(1)) × base × base = (F(2),F(1)) × base2
(F(4),F(3))=(F(2),F(1)) × base3 ...
(F(n), F(n-1)) = (F(n-1), F(n-2)) x {{1,1},{1,0}} = ... = (F(2),F(1))x {{1,1},{1,0}}
于是，求斐波那契数列第N项的问题就变成了如何用最快的方法求一个矩阵的N次方的问题，而求一个矩阵的N次方的问题明显是一个能够在O(logn)时间内解决的问题。
假设要求一个整数的N次方应该如何求解，然后将求整数的N次方的思路应用到求矩阵的N次方就可以了。
如何最快求解10的75次方： 1.75的二进制形式为1001011 2.10的75次方为10^64×10^8×10^2×10^1 于是，首先求出10的1次方，然后根据10的1次方求10的2次方，然后根据10的2次方求10的4次方...以此类推，而64/8/2/1正好对应着75的二进制中1所在的位置表示的数。
对于矩阵的N次方也是如此，例如，muliMatrix方法是矩阵m1和m2相乘，而matrixPower方法是矩阵m的p次方。
- 矩阵乘法函数
public int[][] muliMatrix(int[][] m1, int[][] m2){ int[][] res = new int[m1.length][m2[0].length]; for (int i = 0; i < m1.length; i++) { for (int j = 0; j < m2[0].length; j++) { for (int k = 0; k < m1[0].length; k++) { res[i][j] += m1[i][k] * m2[k][j]; } } } return res; }
- 矩阵乘方函数
public int[][] matrixPower(int[][] m, int p){ int[][] res = new int[m.length][m[0].length]; // 先把res设为单位矩阵，相当于整数中的1 for (int i = 0; i < res.length; i++) res[i][i] = 1; int[][] tmp = m; for (; p != 0; p >>= 1) { if ((p & 1) != 0) { res = muliMatrix(res, tmp); } tmp = muliMatrix(tmp, tmp); } return res; }
和求10的75次方类似，假设要求矩阵m的75次方，那么代码的执行过程是，
首先，75的二进制是：1001011，res为单位矩阵，相当于整数里面的1,
然后p为1001011，tmp = m的1次方，res 为单位矩阵
最右一位是1，res = res * tmp = m的1次方，tmp = m的2次方
最右一位是1，res = res * tmp = m的1+2次方，tmp = m的4次方
最右一位是0，tmp = m的8次方
最有一位是1，res = res * tmp = m的1+2+8次方，tmp = m的16次方
最右一位是0，tmp = m的32次方
最右一位是0，tmp = m的64次方
最右一位是1，res = res * tmp = m的1+2+8+64=75次方，tmp = m的128次方，p == 0， return res即为m的75次方
- 使用矩阵乘法求解斐波那契第N项的主函数
public int fib3(int n) { if (n < 1) return 0; if (n == 1 || n == 2) return 1; int[][] base = {{1,1}, {1,0}}; int[][] res = matrixPower(base, n - 2); return res[0][0] + res[1][0]; }
其中，res的结果就是状态矩阵base的n-2次方，而根据(F(n), F(n-1)) = (F(2),F(1)) x base(n-2) = (1,1) x base(n-2) 就可以知道F(n)就是1*res[0][0] + 1*res[1][0]
二、爬台阶问题
问题：给定整数N，代表台阶数，一次可以爬2个或1个台阶，返回有多少种爬法？例如：N=3，可以1,1,1，也可以2,1，还可以1,2，一共有3种走法，所以返回3。
分析过程：如果台阶只有1级，那么方法只有一种；如果台阶有2级，方法有两种；如果台阶有N级，那么最后一步爬上台阶的方法，要么是从N-2级台阶直接爬到第N级台阶，要么是从N-1级台阶爬到第N级台阶，所以爬上N级台阶的方法数就等于爬上N-2级台阶的方法数加上爬上N-1级台阶的方法数，即F(N) = F(N-1) + F(N-2)，初始项F(1)=1,F(2)=2。可以看出，这和斐波那契数列类似，唯一不同的就是初始项不同，同样根据前4项：1,2,3,5求出状态矩阵（两组方程组，4个等式可以解出4个未知数）base，然后根据(F(n), F(n-1)) = (F(2),F(1)) x base(n-2) = (2,1) x base(n-2) 就可以求出当给定台阶数为N时，一共有多少种爬法。
三、生小牛问题
问题：假设农场中成熟的母牛每年只会生1头小母牛，并且永远不会死。第一年农场只有1只成熟的母牛，从第二年开始，母牛开始生小母牛。每只小母牛3年之后成熟。给定整数N，求出N年后牛的数量。
分析生小牛的过程：1,2,3,4,6,9...N=7时，第7年的总牛数等于第6年的总牛数加上第7年成熟的母牛数，第7年成熟的母牛数又是第4年的总牛数，因此9+4=13
也就是：第N-1年的所有牛都会活到第N年，且第N-3年的所有牛到第N年肯定都是成熟的牛，因此F(N)=F(N-1)+F(N-3)，初始项为F(1)=1,F(2)=2,F(3)=3
N=1，第1年有1头成熟母牛，记为a，总牛数为1 N=2，第2年有1头成熟母牛a，和a新生的小牛，记为b，总牛数为2 N=3，第3年有1头成熟母牛a，和a新生的小牛，记为c，小牛b，c，总牛数为3 N=4，第4年有1头成熟母牛a，和a新生的小牛，记为d，小牛b，c，d，总牛数为4 N=5，第5年有2头成熟母牛a，b，和a，b新生的小牛，记为e，f，小牛c，d，e，f，总牛数为6 N=6，有3头成熟母牛a，b，c，和a，b，c新生的小牛，记为g，h，i，小牛c，e，f，g，h，i总牛数为9 ...
（1）时间复杂度为O(2n)的递归算法
public int cow1(int n) { if (n < 1) return 0; if (n == 1 || n == 2 || n == 3) return n; return cow1(n - 1) + cow1(n - 3); }
（2）时间复杂度为O(n)非递归算法
public int cow2(int n) { if (n < 1) return 0; if (n == 1 || n == 2 || n == 3) return n; int first = 1, second = 2, third = 3; for (int i = 4; i <= n; i++) { int tmp = second; second = third; third = first + third; first = tmp; } return third; }
（3）时间复杂度为O(logn)的状态矩阵乘法算法
根据F(N)=F(N-1)+F(N-3)是一个三阶递推数列，可以知道，一定可以用矩阵乘法表示，而且状态矩阵为3×3的矩阵base。
即（F(N),F(N-1),F(N-2)）= （F(N-1),F(N-2),F(N-3)）× base
把F(1)=1,F(2)=2,F(3)=3,F(4)=4,F(5)=6,带入上面的等式中，可以解得base={{1,1,0},{0,0,1},{1,0,0}}
然后有当n>3时，
n=4，（F(4),F(3),F(2)）= （F(3),F(2),F(1)）× base1
n=5，（F(5),F(4),F(3)）= （F(4),F(3),F(2)）× base1 = （F(3),F(2),F(1)）× base2
n=6，（F(6),F(5),F(4)）= （F(5),F(4),F(3)）× base1 = （F(3),F(2),F(1)）× base3
...
n=n，（F(n),F(n-1),F(n-2)）= （F(3),F(2),F(1)）× basen-3
于是，有使用状态矩阵乘法的算法为：
public int cow3(int n) { if (n < 1) return 0; if (n == 1 || n == 2 || n == 3) return n; int[][] base = {{1,1,0},{0,0,1},{1,0,0}}; int[][] res = matrixPower(base, n - 3); return 3 * res[0][0] + 2 * res[1][0] + 1 * res[2][0]; }
四、总结
如果递归式严格符合F(n) = a×F(n-1) + b×F(n-2) + c×F(n-3) + ... + k×F(n-i)，那么此递归式就是一个i阶的递归式，一定可以写成i×i的状态转移矩阵表达的形式，一律可以用状态转移矩阵乘法然后乘方的方法实现时间复杂度为O(logn)的动态规划算法。