2 动态规划与贪心算法

  动态规划的两个核心：

• 最优子结构性的证明
• 状态转移方程的建立。

  动态规划运行的核心是最优子结构性，证明了这个底层逻辑，动态规划算法就是正确的。

关于本课程的动态规划

  实际上，课程所讲述的动态规划全部属于区间DP，动态规划还有树形DP、状态压缩DP、期望DP等各种各样的形式。使用动态规划算法解决的经典问题：
  一维DP：钢条切割问题。
  二维DP：矩阵链乘法问题、最长公共子序列（LCS，Longest Common Subsequence）问题，最优二叉搜索树问题，0-1背包问题。
  DP维度，就是开辟的DP数组的维数。可能要使用三维DP的问题：POJ 1185。关于这一方面的内容，在这里部署一个动态规划学习。

  贪心算法，在某种程度上可以看做是动态规划的一个特例。动态规划更偏向于穷举，每条路都试一下；贪心算法则是绕开了这种穷举，抄一条近路直接到达目的地，所以很多情况下并不能保证最优解。
  贪心算法运行的核心是贪心选择性质——可以通过做出局部最优解（贪心）来构造全局最优解。只要你证明了这个底层逻辑，贪心算法的正确性一般就能够保证。

  Huffman 树的生成原理，使用了贪心算法：每次调两个最小的结点合并，直到只剩下一个节点，它就是 Huffman 树的根节点。
  图论中也有很多算法的底层逻辑是贪心算法。比如最小生成树的 Prim 算法和 Kruskal 算法，单源最短路径的 Dijkstra 算法。