动态规划与其它算法的关系
    这一章我们将会介绍分治和贪心算法的核心思想，并与动态规划算法进行比较。

    分治
    解决分治问题的时候，思路就是想办法把问题的规模减小，有时候减小一个，有时候减小一半，然后将每个小问题的解以及当前的情况组合起来得出最终的结果。例如归并排序和快速排序，归并排序将要排序的数组平均地分成两半，快速排序将数组随机地分成两半。然后不断地对它们递归地进行处理。

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

    贪心
    关于最优子结构

    贪心：每一步的最优解一定包含上一步的最优解，上一步之前的最优解无需记录
    动态规划：全局最优解中一定包含某个局部最优解，但不一定包含上一步的局部最优解，因此需要记录之前的所有的局部最优解
    关于子问题最优解组合成原问题最优解的组合方式

    贪心：如果把所有的子问题看成一棵树的话，贪心从根出发，每次向下遍历最优子树即可，这里的最优是贪心意义上的最优。此时不需要知道一个节点的所有子树情况，于是构不成一棵完整的树
    动态规划：动态规划需要对每一个子树求最优解，直至下面的每一个叶子的值，最后得到一棵完整的树，在所有子树都得到最优解后，将他们组合成答案
    结果正确性

    贪心不能保证求得的最后解是最佳的，复杂度低
    动态规划本质是穷举法，可以保证结果是最佳的，复杂度高
    分治 动态规划 贪心
    适用类型 通用 优化 优化
    子问题 每个都不同 有很多重复 只有一个
    最优子结构 没有要求 必须满足 必须满足
    子问题数 全部都要解 全部都要解 只解一个
    本 LeetBook 由「力扣」和作者共同制作和发行，版权所有侵权必究。