最近通过各个公司的笔试题发现，好多编程题都是贪心算法和动态规划算法。这两个也容易混淆，在网上也看了好多这两种算法的解析，通过这篇文章写下自己对这两种算法的理解。

使用动态规划的最大特性是原问题的最优解必须包含子问题的最优解。下面通过一个例子解释：求图的最短路径是解释动态规划最容易的问题。下面是一个多段图:

按照贪心算法的思路解决问题可以得到：v1到v2：1到2最短，所以选择2，总长s为2。v2到v3：2到5最短，所以选择5，总长为2+6=8。v3到v4：5到10最短，所以选择10，总长为8+6=14。v4到v5：10到11，总长为14+10=24。所以最短路径为1,2,5,10,11

但是这明显不是最短路径，所以通过贪心算法思路解决的话是错误的。

通过动态规划算法解决多段图最短路径规划问题的思想是，我们要计算每一个子段图到下一个子段图的所有可能的连接情况，并保留每种可能选择中最短的那个连接。

假设我们从终点反推到起点，则具体的操作可以是这样的：

v5到v4有三种路可选：11到8，11到9,11到10。记为{11,8}=6，{11,9}=5，{11,,10}=10.

v4到v3：8到5，8到6，9到6,10到5,10到6,10到7。记最短路径是：8到6，这是最短路径为11到8到6

v3到v2：6到2,6到3,6到4，记最短路径为：6到3，这是最短路径为11到8到6到3.

v2到v1：3到1，这时最短路径为11到8到6到3到1

从而求出多段图的最短路径为{1,3,6,8,11}

从上述推演过程中可以得知动态规划的算法每次都保留所有可能的最优解，那总体最优肯定包含着局部最优。而构成整体最优不一定是由当前最优解构成的。因此需要对全部解决方案进行标记。

一般我们采用动态规划算法解决问题时，首先要明确问题是否具有最优子结构，然后找出问题最优子结构的递推关系式，例如多段图最短路径规划问题中的递推公式可表述如下：

cost(i,j) = min{ c(j,l) + cost(i+1,l) }，l∈Vi+1，(j,l)∈E，E为多段图的边集，Vi+1为第i+1段中的点集

其中cost(i,j)表示的是第i段的第j个顶点到终点t的路径长度的最短值，l为第i+1段中的某个顶点，然后c(j,l)为顶点j到l之间的连接权值，即距离值。

贪心算法的解决思路就是：将问题分解为一个个子问题，找到子问题的最优解，就能得到原问题的最优解。

• 要求解的问题是一个最优化问题；
• 这个问题的解可以用n元组表示；
• 该问题满足最优子结构特性；
• 可以找到最优量度标准，并可以证明该最优量度标准能导致一个整体最优解；
  

适用场景：

1、单源最短路经问题
2、最小生成树问题
3、可任意分割的背包问题。如果不可以任意分割，就需要用动态规划求解。

贪心算法的原型：

• 
  
  SolutionType greedy(int[] a){
  
  
• 
  
  
  
  
• 
  
      // 一开始结果集为空
  
  
• 
  
      SolutionType solution = {};
  
  
• 
  
      // 进行n步选值
  
  
• 
  
      for ( int i=0; i<n; i++ ) {
  
  
• 
  
          // 选出当前局部最优解x
  
  
• 
  
          x = select(a);
  
  
• 
  
          // 判断x是否满足约束条件，若不满足则继续选
  
  
• 
  
          while( !isFeasible(x) ){
  
  
• 
  
              x = select(a);
  
  
• 
  
          }
  
  
• 
  
          // 将当前最优解添加至结果集中
  
  
• 
  
          solution.add(x);
  
  
• 
  
      }
  
  
• 
  
  }
  
  
  

奈斯