算法之动规：将树形结构瓦解

树形结构解斐波那契：

树形原理

---

动规解斐波那契：

动规原理

---

动态规划把原本需要递归的大量数据按照顺序记录下来，

需要使用的时候可以直接调用，

并不需要进行重复计算，

也可以说动规是递归的升华版，

动归相比于递归的优势在于大大降低了程序运行的时间，

在进行较大数据的计算时递归往往会超时，

这时候动归就是最好的选择。

递归源码：

public class Main {

public static void main(String args[]) {

int n = 5;

int[] bak = new int[n + 1];

for (int i = 0; i < n + 1; i++) {

bak[i] = -1;

}

System.out.println(f(n, bak));

}

public static int f(int n, int[] bak) {

if (n == 0) {

return 1;

}

if (n == 1) {

return 1;

}

if (bak[n] != -1) {

return bak[n];

}

int result = f(n - 1, bak) + f(n - 2, bak);

bak[n] = result;

return result;

}

}

动规源码：

public class Main {

public static void main(String args[]) {

int n = 5;

System.out.println(f(n));

}

public static int f(int n) {

if (n == 0) {

return 1;

}

if (n == 1) {

return 1;

}

int result = 0;

int r1 = 1;

int r2 = 1;

for (int i = 2; i <= n; i++) {

result = r1 + r2;

r1 = r2;

r2 = result;

}

return result;

}

}