0003算法笔记——分治法及其在二分搜索中的应用研究意义（棋盘覆盖问题）

1、分治法

分治策略 的核心理念在于，将一个整体规模为n的复杂问题拆解为k个更为简单的子问题，这些子问题 彼此之间不存在依赖关系，并且与原始问题在结构上保持一致 。通过递归的方式逐一求解这些子问题，最终将所有子问题的解进行整合，从而获得原问题的整体解。

适用于分治法处理的问题通常具备以下特点：

1. 当问题的规模缩减至某一特定程度时，能够较为简便地直接求解；
2. 该问题可以被划分为多个规模更小、形式相同的子问题，即该类问题具备最优子结构特性；
3. 通过求解各个子问题所得到的结果能够有效组合，从而形成原问题的完整解答；
4. 所分解出的各个子问题是相互独立的，不会出现重复计算或重叠部分的情况。

分治法实施的主要流程 ：
在每一层递归过程中，分治法通常遵循三个基本操作步骤：
** 分解 **：将原始复杂的问题拆分为若干个较小、彼此独立且与原问题具有相同形式的子任务；
** 解决 **：若当前分解后的子任务足够简单可直接求解，则立即处理；若仍较复杂，则继续采用递归方式对其进一步分解并求解；
** 合并 **：将各个已经解决的子任务结果进行综合处理，最终还原为原始问题的整体答案。
其通用的算法设计框架如下：

 　　Divide-and-Conquer(P)

    
 　　1.