数据结构与算法 - 动态规划(简介)

转载说明

动态规划与其它算法的关系

分治

解决分治问题的时候,思路就是想办法把问题的规模减小,有时候减小一个,有时候减小一半,然后将每个小问题的解以及当前的情况组合起来得出最终的结果。

例如归并排序和快速排序,归并排序将要排序的数组平均地分成两半,快速排序将数组随机地分成两半。 然后不断地对它们递归地进行处理。

这里存在有最优的子结构,即原数组的排序结果是在子数组排序的结果上组合出来的,但是不存在重复子问题,因为不断地对待排序的数组进行对半分的时候,两半边的数据并不重叠,分别解决左半边和右半边的两个子问题的时候,没有子问题重复出现,这是动态规划和分治的区别。

贪心

关于最优子结构

贪心:每一步的最优解一定包含上一步的最优解,上一步之前的最优解无需记录

动态规划:全局最优解中一定包含某个局部最优解,但不一定包含上一步的局部最优解,因此需要记录之前的所有的局部最优解

关于子问题最优解组合成原问题最优解的组合方式

贪心:如果把所有的子问题看成一棵树的话,贪心从根出发,每次向下遍历最优子树即可,这里的最优是贪心意义上的最优。此时不需要知道一个节点的所有子树情况,于是构不成一棵完整的树

动态规划:动态规划需要对每一个子树求最优解,直至下面的每一个叶子的值,最后得到一棵完整的树,在所有子树都得到最优解后,将他们组合成答案

结果正确性

贪心不能保证求得的最后解是最佳的,复杂度低

动态规划本质是穷举法,可以保证结果是最佳的,复杂度高

分治 动态规划 贪心
适用类型 通用 优化 优化
子问题 每个都不同 有很多重复 只有一个
最优子结构 没有要求 必须满足 必须满足
子问题数 全部都要解 全部都要解 只解一个

推荐阅读顺序

  1. 数据结构与算法 - 动态规划(简介)
  2. 数据结构与算法 - 动态规划(线性动态规划)
  3. 数据结构与算法 - 动态规划(前缀和)
  4. 数据结构与算法 - 动态规划(区间动态规划)
  5. 数据结构与算法 - 动态规划(背包问题)
  6. 数据结构与算法 - 动态规划(状态压缩)
  7. 数据结构与算法 - 动态规划(计数问题)
  8. 数据结构与算法 - 矩阵快速幂
  9. 数据结构与算法 - 动态规划(数位动态规划)