看这篇文章前先看一下第一篇文章：

斐波那契数列数列相关简化1_鱼跃鹰飞的博客-CSDN博客

根据第一篇文章总结如下：

如果某个递归，除了初始项之外，具有如下的形式

F(N) = C1 * F(N) + C2 * F(N-1) + … + Ck * F(N-k) ( C1…Ck 和k都是常数)

并且这个递归的表达式是严格的、不随条件转移的

那么都存在类似斐波那契数列的优化，时间复杂度都能优化成O(logN)

练一个新的题目：

第一年农场有1只成熟的母牛A，往后的每年：

1）每一只成熟的母牛都会生一只母牛

2）每一只新出生的母牛都在出生的第三年成熟

3）每一只母牛永远不会死

返回N年后牛的数量

 

直接上代码吧，里面有详细的注释：

package dataStructure.fibonacci;/*** 第一年农场有1只成熟的母牛A，往后的每年：** 1）每一只成熟的母牛都会生一只母牛** 2）每一只新出生的母牛都在出生的第三年成熟** 3）每一只母牛永远不会死** 返回N年后牛的数量*/
public class HowManyCowsLeft {public static int howManyCows(int n) {if(n < 1) return 1;if(n <= 4) return n;//根据枚举找到的规律或者说可以根据满3年可以生孩子进行的推算，f(n-1)是上一年的//f(n-3)是3年前的奶牛数量，3年前的今年都可以生小奶牛了return howManyCows(n - 1) + howManyCows(n-3);}public static int howManyCows2(int n) {if(n < 1) return 1;if(n <= 4) return n;//return howManyCows(n - 1) + howManyCows(n-3);// 根据我们之前斐波那契数列数量的经验，这个是有严格推理结构的，没有任何条件的推理//最多依赖n-3这应该是一个3阶矩阵//|f(4) f(3) f(2)| = f|f(3) f(2) f(1)| * {{a,b,c},{d,e,f},{g,h,i}}//|4,3,2| = |3,2,1| * {{a,b,c},{d,e,f},{g,h,i}}->3a+2b+c=4 3d+2e+f=3 3g+2h+i=2//|f(5) f(4) f(3)| = f|f(4) f(3) f(2)| * {{a,b,c},{d,e,f},{g,h,i}}//|6,4,3| = |4,3,2| * {{a,b,c},{d,e,f},{g,h,i}}->4a+3b+2c=6 4d+3e+2f=4 4g+3h+2i=3//|f(6) f(5) f(4)| = f|f(5) f(4) f(3)| * {{a,b,c},{d,e,f},{g,h,i}}//|9,6,4| = |6,4,3| * {{a,b,c},{d,e,f},{g,h,i}}->6a+4b+3c=9 6d+4e+3f=6 6g+4h+3i=4//通过上面三个方程就可以得出a=1，b=0,c=1 d=1, e=0, f=0, g=0, h=1, i = 0//也就是说这个问题的base矩阵就是{{1,0,1},{1,0,0},{0,1,0}}//|f(n) f(n-1) f(n-2)| = |f(3) f(2) f(1)| * base的n-3次方//先求base的n-3次方int[][] base = {{1,0,1},{1,0,0},{0,1,0}};int[][] matrix = matrixPower(base, n - 3);int[][] matrix321 = {{3,2,1}};matrix = product(matrix321, matrix);return matrix[0][0];}private static int[][] product(int[][] matrix1, int[][] matrix2) {if(matrix1 == null || matrix2 == null || matrix1[0].length == 0 || matrix1[0].length != matrix2.length) {return null;}//n是matrix1的行数int n = matrix1.length;//m是matrix2的列数int m = matrix2[0].length;//k是matrix1的列数，这个数同时也等于matrix2的行数int k = matrix1[0].length;int[][] matrix = new int[n][m];for(int i = 0; i < n; i++) {for(int j = 0; j < m; j++) {matrix[i][j] = 0;for(int k1 = 0; k1 < k; k1++) {matrix[i][j] += matrix1[i][k1] * matrix2[k1][j];}}}return matrix;}private static int[][] matrixPower(int[][] base, int q) {int[][] matrix = {{1,0,0},{0,1,0},{0,0,1}};int[][] t = base;for(; q != 0; q >>= 1) {if((q & 1) != 0) {matrix = product(matrix, t);}t = product(t, t);}return matrix;}public static void main(String[] args) {int n = 6;int numsOfCows = howManyCows(n);System.out.println(numsOfCows);int numsOfCows2 = howManyCows2(n);System.out.println(numsOfCows2);}}

属于类似的套路，应该比较好理解，欢迎私信交流