外观
分治、动态规划和贪心怎么区分？
分治把问题拆成互不重叠的子问题，分别解决再合并，例如归并排序。动态规划的子问题会重叠，所以把结果存下来。贪心每步选当前看起来最好的，而且必须能证明局部选择不会挡掉全局最优。
原理
分治的递归树里，子问题独立。快排、归并都是。合并成本要算进复杂度。
动态规划先定义状态，再写转移。例如爬楼梯，到第 n 级的方法数等于到 n-1 和 n-2 的方法数之和。自顶向下是带缓存的递归，自底向上是循环填表。能滚动数组时，空间可以从 O(n) 降到 O(1)。
贪心的例子是按结束时间选会议：每次选结束最早、且不和已选冲突的那场。它不回头。如果举不出交换论证或反例，就不要声称贪心正确，改用动态规划或搜索。
回溯是搜索：做选择、递归、撤销选择。排列、组合、棋盘问题常用它。复杂度往往是指数，要用剪枝说明哪些分支可以不走。
追问
重叠子问题最优子结构呢？
最优子结构是大问题的最优解能由子问题的最优解组成。重叠是指递归过程中同一个子问题出现多次。两个都有，才值得做动态规划。只有最优子结构、子问题不重叠，分治就够。
怎么判断该用贪心？
先找反例。反例一出现就放弃贪心。找不到反例时，再尝试说明交换任意一个选择都不会更好。
易错点
- 把所有递归都叫动态规划。没有缓存或填表，就只是递归。
- 贪心题目不证明，只说「每步选最大的」。
- 回溯忘记撤销选择，下一轮分支看到了不该共享的状态。