动态规划算法中在所有的基础算法中是比较难以理解的算法，可能需要通过几篇文章来聊一聊。 动态规划的算法常有一堆名词比如最优子结构，动态转移方程，导致的理解起来难度更大，直到我看到网上有一篇关于动态规划的套路，比在极客时间里面学习的动态规划算法更简单。
通过这么长的时间的算法学习，了解到算法发明特别是牛逼的算法比如BM算法等，大多数不是一蹴而就的，都是在前人基础上的迭代或更进一步。刚开始的解决问题的算法都是比较直观的算法，比较暴力的算法。
比如动态规划算法一般遵循一套固定的套路：暴力破解算法->带备忘录的递归算法->非递归的动态规划算法。
以上一篇斐波那契数列为例来介绍下动态规划算法，上篇已经对这个数列进行了介绍，这个数列的特点用下面的算式来替代：
暴力破解法
先用暴力的递归编码实现：
public class Func {
static int fib(int n) {
if (n == 1|| n==2){
return 1;
}else {
return fib(n-1)+fib(n-2);
}
}
public static void main(String args[]) {
System.out.println(Func.fib(6));
}
}
这段代码很简洁，也很容易懂，但是效率有点低，可以通过画图的方法来分析下为什么这段代码的执行效率比较低：
通过这部分执行图可以看出，F(6)重复计算了2次，F(5)重复计算了3次等。 既然都计算过了，我们是不是可以通过一个数组来保存起来中间结果，在每次计算之前先判断下数组中是否有值，没有就计算，有就直接返回了，岂不是节省了计算时间。
带备忘录的暴力破解法
import java.util.Arrays;
public class Func {
static int [] arr = null;
static int fib(int n) {
if (n == 1|| n==2){
return 1;
}else {
if (arr == null) {
arr = new int[n+1];
Arrays.fill(arr, 0);
}else {
if (arr[n] != 0) {
System.out.println("Return quick :"+n);
return arr[n];
}
}
int res = fib(n-1)+fib(n-2);
arr[n] = res;
return res;
}
}
public static void main(String args[]) {
System.out.println(Func.fib(6));
}
}
从图中可以看出，首先绿色节点f(2)和f(1)均不需要计算，红色节点是通过查表得到的，浅绿色的节点是真正需要计算的：f(3),f(4),f(5)... 这样通过增加备忘录，我们将一颗递归树进行了裁剪，递归的算法时间复杂度=子问题的个数*每个子问题的求解复杂度，子问题复杂度本身为O（1），而子问题又没有存在冗余，所以整体的算法的复杂度为O（n），到此为止的话这种计算方法和递归的性能来说已经很接近了，只是递归的算法我们是从上到下执行，然后再从下到上返回，动态规划却不一样。
动态规划
有了上面的启发，我们根据斐波那契数列的递推公式，可以很简单的来想为什么不直接依次计算那，我们把备忘录独立成一张表叫做：DPtable。
static int fib2( int n) {
int [] arr2 = new int[n+1];
arr2[1] = 1;
arr2[2] = 1;
for (int i =3; i<= n ;i++) {
arr2[i] = arr2[i-1]+arr2[i-2];
}
return arr2[n];
}
这个算法和刚才的带备忘录的递归算法的基本一样的，只是这种是从下对上的计算方式。 这里面的核心部分：arr2[i] = arr2[i-1]+arr2[i-2]; 就是状态转移方程，可以将数组的一个值标识一种状态，后面的状态是前面的两种状态转移过去的。 再进一步优化，其实数列的状态只和前两个状态有关，所以不需要这么长的数组，可以进一步缩小存储空间：
static int fib3( int n) {
int pre = 1;
int curr = 1;
for (int i =3; i<= n ;i++) {
int sum = pre+curr;
pre = curr;
curr = sum;
}
return curr;
}
整个算法的空间复杂度优化到了O(1)。
好了，就聊到这里了，祝大家周末愉快。
快到十一了，祝大家国庆节快乐！