苏州大型网站建设公司,wordpress 搜索引擎收录,网站建设考虑,品牌建设案例学计算机的对这道题肯定不陌生#xff0c;我记得是学C语言的时候学递归的时候有这道题#xff0c;于是我就世界用递归写了如下代码#xff1a;
class Solution {public int fib(int n) {if(n1) return 1;if(n0) return 0;return (fib(n-1) fib(n-2)) % 1000000007;}
}
到… 学计算机的对这道题肯定不陌生我记得是学C语言的时候学递归的时候有这道题于是我就世界用递归写了如下代码
class Solution {public int fib(int n) {if(n1) return 1;if(n0) return 0;return (fib(n-1) fib(n-2)) % 1000000007;}
}
到n44就算不出了超时了。就看了一下题解题解用的是动态规划的方法
class Solution {public int fib(int n) {if(n2){return n;}int p0,q1;int r 0;for(int i 2;in;i){r (pq) % 1000000007;p q;q r; }return r;}
}
n小于2的话返回自己然后定义p为n的前两个数q为n的前一个数然后r是第n个数的值所以r就等于pq然后把q给pr给q最后返回r就可以了。
题解还给出了一种矩阵幂的方法 最后只需要求M的n次方就行。
class Solution {static final int MOD 1000000007;public int fib(int n) {if (n 2) {return n;}int[][] q {{1, 1}, {1, 0}};int[][] res pow(q, n - 1);return res[0][0];}public int[][] pow(int[][] a, int n) {int[][] ret {{1, 0}, {0, 1}};while (n 0) {if ((n 1) 1) {ret multiply(ret, a);}n 1;a multiply(a, a);}return ret;}public int[][] multiply(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]) % MOD);}}return c;}
}
定义了一个矩阵乘矩阵的multiply方法求矩阵的n次方的pow方法通过这两个方法可以求出M的n次方。
