分治法

分治法

将一个大问题分成多个子问题的,把这些小的易求解的子问题解决出来，大问题也就解决了

什么时候使用

问题缩小到一定规模容易解决分解的子问题是相同种类的子问题，即该问题具有最优子结构分解后的子问题可以合并子问题的作用区间不重复

其中第第一条基本都能满足，第二条反应的的递归的思想也容易满足，第三条是能否使用分治的关键 如果不满足第三条可以是考虑贪心或者dp，第四条不满足也可以进行分治，但是会浪费时间，可以考虑dp