动态规划01

一、什么是动态规划

　　动态规划是一种用来解决一类最优化问题的算法思想。将一个复杂的问题分解成若干个子问题（有点像分治），然后综合子问题的最优解找到原问题的最优解（这里有点像贪心）。在求解每个子问题的时候，每个求解过的子问题会被记录下来，在求解同样的子问题时就会直接读取上次被记录的结果，从而免去了重复的计算。因为动态规划采用了分治思想，所以可以用递归来实现。当然也可以用递推方式实现。

二、动态规划的递归写法

 　　斐波那契数列就是一个典型的例子，定义为：F(n)=F(n-1)+F(n-2)（n>=2），F1=1，F0=1。求斐波那契的递归写法也很常见，只要把数学上的函数转为逻辑上的代码就可以了。

　　朴素算法：

int F(n){
  if(n==0 || n==1) return 1;
    else return F(n-1)+F(n-2);
}

　　下面可以模拟一下这个算法，假设求n=4，会得出以下过程

　　F(4)=F(3)+F(2) 向下递归

　　F(3)=F(2)+F(1)；F(2)=F(1)+F(0)向下递归

　　F(2)=F(1)+F(0)向下递归

　　F(1)=1;F(0)=1;向上返回

　　其实使用一颗递归树能更直观的感受该代码

 　　很明显F(2)的值被计算了两次，而事实上随着n的增大重复计算的次数会越来越多，而这颗递归树会像一颗完全二叉树一样，注意，仅仅是趋于一颗完全二叉树，可以把F(4)这颗树想象成F(5)的一颗子树，F(5)的另一颗子树其实就是F(3)，显然F(3)也是F(4)的一颗子树，所以有两颗重复子树在一棵树中，这大大增加了运行时间。

　　对于朴素算法的时间复杂度分析，可以通过这颗递归树来算一下，每个节点只包含常数次的运算，而递归二叉树的高度是n，所以节点数近似等于2^n，所以时间复杂度可是用O(2^n)来表示。

　　采用动态规划的斐波那契数列

　　可以申请一块大小为n的存储空间，这些空间用来存放F(n)各个子树的值，当要再次求相同子树时可以直接从相应位置取值

int F(int n){
    if(n==0 || n==1) return 1;
    else if(dp[n] != -1) return dp[n];
    else {
        dp[n] = F(n-1)+F(n-2);
        return dp[n];
    }
}

　　开始时可以构造一个数组dp[n]，数组元素值用-1初始化。通过这个数组就将程序的时间复杂度降到了O(n)的级别