算法设计方法3：动态规划_动态规划算法的概念是什么

前言：动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。在各大公司的笔试题中，有关动态规划的题目会经常出现。有很多问题，用贪婪法和分治法无法简洁而高效的解决，但是用动态规划就可以。比如0/1背包问题，其中物品不可拆分，使用贪婪法可能不能得到最优解。但是贪心算法适用于可拆分的物品的背包问题，通过性价比排名就可以进行更好的选择。

一、动态规划的概念

1、什么是动态规划

①定义

动态规划是求解决策过程最优化的数学方法。把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。动态规划算法通常基于一个递推公式及一个或多个初始状态，当前子问题的解将由上一次子问题的解推出。

动态规划同分支法一样是通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法，动态规划常常适用于有重叠子问题和最优子结构性质的问题。

问题特征

最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。

重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。(比如斐波那契数列递归求解算法中)

总结：若要解一个给定问题，我们先计算其子问题，再由子问题计算父问题。 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量： 一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。

一般需要恰当定义子问题“规模”的概念，使得任何子问题的求解都只依赖于“更小的”子问题的求解。因此，我们可以将子问题按照规模顺序，由小至大顺序进行求解。当求解某个子问题时，它所依赖的那些更小的子问题都已求解完毕，结果已经保存。每个子问题只需求解一次，当我们求解它时，它的所有前提子问题都已求解完成。

2、分治与动态规划区别

共同点：二者都要求原问题具有最优子结构性质,都是将原问题分而治之,分解成若干个规模较小(小到很容易解决的程序)的子问题，然后将子问题的解合并,形成原问题的解。

不同点：分治法将分解后的子问题看成相互独立的，通过用递归来做。

　　　  动态规划将分解后的子问题理解为相互间有联系,有重叠部分，需要记忆，通常用迭代来做。

总结： 动态规划和分治法相似，都是通过组合子问题的解来求解原问题。分治法将问题划分成互不相交的子问题，递归求解子问题，再将他们的解组合起来，求出原问题的解。与之相反，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题。在这种情况下，分治算法会做出许多不必要的工作，它会反复的求解那些公共子问题。而动态规划算法对每个子子问题只求解一次，将结果保存到表格中，以免在递归的过程中重复计算，从而减少了计算量。

3、什么时候要用动态规划？

如果要求一个问题的最优解（通常是最大值或者最小值），而且该问题能够分解成若干个子问题，并且小问题之间也存在重叠的子问题，则考虑采用动态规划。

注意：动态规划从来没有说是专门用来做优化的，本质上dp算法是一种高效的枚举算法，只不过有时我们的问题是找出所有可能枚举值中满足某个最优条件的那个状态，所有很多没有经过系统的运筹学数学知识培养的同学会把dp纯粹当成了优化问题的算法。许多非优化问题，比如需要枚举出所有可能结果的问题，dp是非常适用的。常见的问题有八皇后问题，中国象棋马的可能路径问题，所有回文子序列（子串）问题等。

4、怎么使用动态规划？
我把下面称为动态规划五部曲：

1. 判题题意是否为找出一个问题的最优解
2. 从上往下分析问题，大问题可以分解为子问题，子问题中还有更小的子问题
3. 从下往上分析问题 ，找出这些问题之间的关联（状态转移方程），如何从一个或多个已知状态求出另一个未知状态的值。（递推型）
4. 讨论底层的边界问题，确定一些初始状态（边界状态）的值，并用数组存起初始子问题的解
5. 解决问题（通常使用数组进行迭代求出最优解）

5、动态规划算法的核心

A ：1+1+1+1+1+1+1+1 =？请问该等式的值是多少？

B : 计算得出为 8!

A ：在上面等式的左边写上 "1+" ，此时等式的值为多少？

B: So easy，9!

A : 你怎么这么快就知道答案啦？

B : 只要在8的基础上加1就行了！

A : 所以你不用重新计算，因为你记住了第一个等式的值为8!动态规划算法也可以说是“记住求过的解来节省时间”。

动态规划算法的核心就是记住已经解决过的子问题的解，以便下次需要时直接查表使用。

6、动态规划的分类

动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类。

举例：

线性动规：拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等；

区域动规：石子合并， 加分二叉树，统计单词个数，炮兵布阵等；

树形动规：贪吃的九头龙，二分查找树，聚会的欢乐，数字三角形等；

背包问题：01背包问题，完全背包问题，分组背包问题，二维背包，装箱问题，挤牛奶(同济ACM第1132题）等；

应用实例：

常见的有背包问题、钢条切割、青蛙跳台阶、过桥用时最短问题、最短路径问题 、网络流优化等，还有字符串处理中的最长公共子序列（不连续）、最长公共子串（连续）和最长回子字串问题。

二、动态规划算法的两种形式

上面已经知道动态规划算法的核心是记住已经求过的解，记住求解的方式有两种：①自顶向下的备忘录法 ②自底向上。
为了说明动态规划的这两种方法，举一个最简单的例子：求斐波拉契数列Fibonacci 。

问题描述：斐波那契数列，又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。指的是这样一个数列：1，1，2，3，5，8，13，21，34，55，89，144……依次类推下去。你会发现，这个数列从第3项开始，每一项都等于前两项之和。在这个数列中的数字，就被称为斐波那契数。

前面博客写过的递归版本很简单：

public int fib(int n)
{
    if(n<=0)
        return 0;
    if(n==1)
        return 1;
    return fib( n-1)+fib(n-2);
}
//输入：6
//输出：8

先来分析一下递归算法的执行流程，假如输入6，那么执行的递归树如下：

上面的递归树中的每一个子节点都会执行一次，很多重复的节点被执行，fib(2)被重复执行了5次。由于调用每一个函数的时候都要保留上下文，所以空间上开销也不小。这么多的子节点被重复执行，如果在执行的时候把执行过的子节点保存起来，后面要用到的时候直接查表调用的话可以节约大量的时间。下面就看看动态规划的两种方法怎样来解决斐波拉契数列Fibonacci 数列问题。
①自顶向下的备忘录法

public static int Fibonacci(int n) 
{ 
   if(n<=0) 
   return n; 
   int [] Memo = new int[n+1];
   for(int i=0;i<=n;i++)
        Memo[i]=-1; 
 
    return fib(n, Memo); 
}
 
 public static int fib(int n,int []Memo) 
{ 
   if(Memo[n]!=-1) return Memo[n];
   //如果已经求出了fib（n）的值直接返回，否则将求出的值保存在Memo备忘录中。               
   if(n<=2)
     Memo[n]=1; 
   else 
     Memo[n]=fib( n-1,Memo)+fib(n-2,Memo); 
 
   return Memo[n]; 
}

备忘录法也是比较好理解的，创建了一个n+1大小的数组来保存求出的斐波拉契数列中的每一个值，在递归的时候如果发现前面fib（n）的值计算出来了就不再计算，如果未计算出来，则计算出来后保存在Memo数组中，下次在调用fib（n）的时候就不会重新递归了。比如上面的递归树中在计算fib（6）的时候先计算fib（5），调用fib（5）算出了fib（4）后，fib（6）再调用fib（4）就不会在递归fib（4）的子树了，因为fib（4）的值已经保存在Memo[4]中。

②自底向上的动态规划

备忘录法还是利用了递归，上面算法不管怎样，计算fib（6）的时候最后还是要计算出fib（1），fib（2），fib（3）……,那么何不先计算出fib（1），fib（2），fib（3）……,呢？这也就是动态规划的核心，先计算子问题，再由子问题计算父问题。

public static int fib(int n)
{
        if(n<=0)
            return n;
        int[] Memo = new int[n+1];
        Memo[0]=0;
        Memo[1]=1;
        for(int i=2;i<=n;i++)
        {
            Memo[i]=Memo[i-1]+Memo[i-2];
        }       
        return Memo[n];
}

一般来说由于备忘录方式的动态规划方法使用了递归，递归的时候会产生额外的开销，使用自底向上的动态规划方法要比备忘录方法好。

总结：这种自下向上的动态规划方法一般需要恰当定义子问题“规模”的概念，使得任何子问题的求解都只依赖于“更小的”子问题的求解。因此，我们可以将子问题按照规模顺序，由小至大顺序进行求解。当求解某个子问题时，它所依赖的那些更小的子问题都已求解完毕，结果已经保存。每个子问题只需求解一次，当我们求解它时，它的所有前提子问题都已求解完成。

三、动态规划小试牛刀

《算法导论》上的例题：钢条切割问题

问题描述：Serling公司购买长钢条，将其切割为短钢条出售。切割工序本身没有成本支出。公司管理层希望知道最佳的切割方案。假定我们知道Serling公司出售一段长为i英寸的钢条的价格为pi(i=1,2,…，单位为美元)。钢条的长度均为整英寸。图15-1给出了一个价格表的样例。

钢条切割问题是这样的：给定一段长度为n英寸的钢条和一个价格表pi(i=1,2,…n)，求切割钢条方案，使得销售收益rn最大。注意，如果长度为n英寸的钢条的价格pn足够大，最优解可能就是完全不需要切割。

问题分析：

Java代码：

1、朴素递归算法

public static int cut(int[] p,int n) 
{ 
    if(n==0)
       return 0; 
 
    int q = -1;
 
    for (int i = 1; i <= n; ++i)
    {
        int tmp = p[i-1] + cut(p, n - i);
        if (q < tmp)
        {
            q = tmp;
        }
    }
 
  return q; 
}

递归很好理解，如果不懂可以看上面的讲解，递归的思路其实和回溯法是一样的，遍历所有解空间。但这里和上面斐波拉契数列的不同之处在于，在每一层上都进行了一次最优解的选择。q=Math.max(q, p[i-1]+cut(p, n-i));这个段语句就是最优解选择，这里上一层的最优解与下一层的最优解相关。

2、动态规划算法

朴素递归算法之所以效率很低，是因为它反复求解相同的子问题。因此，动态规划方法仔细安排求解顺序，对每个子问题只求解一次，并将结果保存下来。如果随后再次需要此子问题的解，只需查找保存的结果，而不必重新计算。因此，动态规划方法是付出额外的内存空间来节省计算空间。

public static int buttom_up_cut(int[] p,int n) 
{ 
    int [] r = new int[p.length+1];
    for(int i=1;i<=n;i++) 
    {
       int q=-1;
       //①
       for(int j=1;j<=i;j++) 
          q = Math.max(q, p[j-1]+r[i-j]);
 
       r[i]=q;
    } 
 
    return r[p.length]; 
}

自底向上的动态规划问题中最重要的是理解注释①处的循环，这里外面的循环是求r[1],r[2]……，里面的循环是求出r[1],r[2]……的最优解，也就是说r[i]中保存的是钢条长度为i时划分的最优解，这里面涉及到了最优子结构问题，也就是一个问题取最优解的时候，它的子问题也一定要取得最优解。下面是长度为4的钢条划分的结构图。我就偷懒截了个图。

参考链接：

动态规划从入门到精通（一）-入门篇

算法-动态规划 Dynamic Programming--从菜鸟到老鸟

动态规划经典实例