02_divide_n_conquer.md

Table of Contents generated with DocToc

• 分治法（Divide-and-Conquer Algorithm）
  • 分治与动态规划
  • 分类
  • 应用
  • 参考

分治法（Divide-and-Conquer Algorithm）

分治分治，即分而治之。分治，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

分治与动态规划

当子问题相互独立时，能且只能使用分治。存在重叠子问题时，动态规划是更好的算法。 In a word, 分治法 —— 各子问题独立；动态规划 —— 各子问题重叠。

分类

• 递归分治

• 非递归分治 !

应用

1. 最大值和最小值 改进:区分问题

改进：分组

参考