分治策略

将原问题分解为若干个规模较小但类似于原问题的子问题（Divide），递归的求解这些子问题（Conquer），然后再合并这些子问题的解来建立原问题的解。因为在求解大问题时，需要递归的求小问题，因此一般用递归的方法实现，即自顶向下。

动态规划

动态规划所解决的问题是分治策略所解决问题的一个子集，只是这个子集更适合用动态规划来解决从而得到更小的运行时间。即用动态规划能解决的问题分治策略肯定能解决，只是运行时间长了。因此，分治策略一般用来解决子问题相互对立的问题，称为标准分治，而动态规划用来解决子问题重叠的问题。
动态规划一般由两种方法来实现，一种为自顶向下的备忘录方式，用递归实现，一种为自底向上的方式，用迭代实现。

贪心算法

贪心算法在每一步都做出最优的选择，希望这样的选择能导致全局最优解。

总结

  1. 分治策略用于解决原问题与子问题结构相似的问题，对于各子问题相互独立的情况，一般用递归实现；
  2. 动态规划用于解决子问题有重复求解的情况，既可以用递归实现，也可以用迭代实现；
  3. 贪心算法用于解决具有贪心选择性质的一类问题，既可以用递归实现，也可以用迭代实现，因为很多递归贪心算法都是尾递归，很容易改成迭代贪心算法；
  4. 递归是实现手段，分治策略是解决问题的思想，动态规划很多时候会使用记录子问题运算结果的递归实现。

联系作者