1. 分治法

1.1. 含义

分而治之

将原问题分解成与原问题相同但是规模更小的子问题,可以反复执行这个过程, 使得问题规模减小到可以求解为止.

1.2. 案例

1. 快速排序

给定1000个数, 从小到大进行排序

1. 凯苏傅里叶变换算法
2. Karatsuba 大数乘法算法

1.3. 关键点

1. 数学归纳是使用分治思想

只要出现可以用数学归纳公式来表示的大规模问题, 第一反应就是分治算法,通过特定的函数参数安排, 肯定可以套用递归结构

1. 分治思想不一定使用递归结构

递归结构是循环结构的一种, 所以分治思想也可以是循环结构

1. 分治思想的核心是如何分

1.4. 流程

• 划分问题: 整个问题划分成多个无关联的子问题
• 递归求解: 递归调用求解各个子问题
• 合并问题: 合并子问题的解, 形成原始问题的解

1.5. 使用条件

1. 问题缩小到一定规模就可以很容易解决
2. 问题可以拆分成若干个小问题
3. 子问题的解可以合并成该问题的解
4. 同一层分解出来的子问题是相互独立的(子问题之间不包含公共的子问题)(非必须)

条件2, 3 是分治的前提, 即必要条件. 第4条, 对于存在公共子问题的问题, 使用分治算法会存在重复计算的问题, 使用DP较为合适

1.6. 分治和DP的共同点和不同点

1.6.1. 分治法

各子问题独立

1.6.2. 动态规划

各子问题重叠