对于递归的优化过程
- 暴力递归
- 对于暴力递归，某些计算过程是重复的，因此可以优化成记忆化递归。
- 而对于递归问题，一般都可以转换为动态规划。
- 而对于动态规划，我们又可以对dp数组进行优化，比如滚动数组的思想，可以将二维dp数组优化为一维dp数组，可以将一维dp数组优化为几个变量。
暴力递归
public int fibonaci(int n) {
if (n <= 0) {
return 0;
}
if (n == 1 || n == 2) {
return 1;
}
return fibonaci(n - 1) + fibonaci(n - 2);
}
对于暴力递归，我们的fibonaci(n – 1)和fibonaci(n – 2)有很多重复计算，我们要想办法把已经计算过的结果都存储起来！
记忆化递归
public int fibonaci2(int n) {
if (n <= 0) {
return 0;
}
int[] memories = new int[n + 1];
return process2(n, memories);
}
private int process2(int n, int[] memories) {
int res = 0;
// 如果memories中有记录，则直接return
if (memories[n] != 0) {
return memories[n];
}
if (n == 1 || n == 2) {
res = 1;
}
if (n > 2){
res = process2(n - 1, memories) + process2(n - 2, memories);
}
memories[n] = res;
return res;
}
现在我们将已经已经计算过得结果放在memories中。如果memories中有记录，就不需要再去递归做重复计算。
动态规划
public int fibonaci3(int n) {
if (n <= 0) {
return 0;
}
if (n == 1 || n == 2) {
return 1;
}
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 1;
for (int i = 3; i <= n; i++) {
dp[i] = (dp[i - 1] + dp[i - 2]);
}
return dp[n];
}
动态规划的优化，滚动数组的思想
当然这题的dp数组是一维的，所以我们只需要几个变量来滚动向前就行了。
最小路径和这题的dp数组就是二维的，所以优化的话就是使用一维滚动数组。
public int fibonaci4(int n) {
if (n <= 0) {
return 0;
}
if (n == 1 || n == 2) {
return 1;
}
int tmp;
int pre = 1;
int cur = 1;
for (int i = 3; i <= n; i++) {
tmp = cur;
cur = pre + cur;
pre = tmp;
}
return cur;
}
番外篇：快速幂
左神的书中的特别解法，这种解法是用了某些数学定理。定理说F(N)=F(N-1)+F(N-2)是严格的递推公式，所以一定有(F(n), F(n-1)) = (F(n-1), F(n-2)) * [[a, b], [c, d]]，状态矩阵： [[a, b], [c, d]]。带入f(1)，f(2)，f(3)，f(4)等，可以求出状态矩阵为{{1, 1}, {1, 0}}。
\[(F(n),F(n-1))=(1,1)*\begin{vmatrix}1 & 1 \\ 1 & 0\\ \end{vmatrix}^{n-2}
\]
\]
要求F(n)则变为求矩阵的幂。
而不论求一个数字的幂，还是求矩阵的幂，我们都有一个方法叫快速幂。不会快速幂的同学，可以先看看如何求一个数字的幂，再来看矩阵的，代码基本一样。
// 快速幂求矩阵的幂
public int[][] matrixPower(int[][] m, int p) {
int[][] res = new int[m.length][m[0].length];
// 初始化为单位矩阵
for (int i = 0; i < res.length; i++) {
res[i][i] = 1;
}
int[][] tmp = m;
for (; p != 0; p >>= 1) {
if ((p & 1) == 1) {
res = muliMatrix(res, tmp);
}
tmp = muliMatrix(tmp, tmp);
}
return res;
}
// 矩阵乘法计算
private 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 < m2.length; k++) {
res[i][j] += m1[i][k] * m2[k][j];
}
}
}
return res;
}
public int fibonaci5(int n) {
if (n <= 0) {
return 0;
}
if (n == 1 || n == 2) {
return 1;
}
int[][] res = matrixPower(new int[][]{{1, 1}, {1, 0}}, n - 2);
return 1 * res[0][0] + 1 * res[1][0]; // 这一行不懂的往上看看数学公式。
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/195938.html
