分治算法最重要的就是如何确定好划分方式，以及划分的构造

Theory&Thinkings #

分而治之 #

分解为性质相同的子问题，应该只是规模不同

如果性质不同怎么办？
- 进行预处理，转化为性质相同的子问题

归并排序

分治的分：不同的划分方法

黑盒划分：归并排序，逆序对
白盒划分：快速排序

平衡子问题

减而治之

当分出的子问题是完全相同时，避免重复递归调用
直到某个子问题不用递归求解
直接舍弃或者使用
减是精髓

快速排序中的划分 partition非常重要

快速归并排序 #enlighten

思考方法：先把题目降维，然后进行处理

递归三要素：

递归终止条件：递归需要一个明确的临界点，程序一旦到达了这个临界点，就不用继续往下递归，防止无限递归
终止处理办法：在递归的临界点对应一种简单的情景，这种情景下，应当直接给出问题的解决方案
递归处理方法：递归问题必须可以分解为若干个规模较小、与原问题形式相同的子问题，这些子问题可以用相同的思路来解决，并且合并得到原问题答案。

递归与循环

递归也是一种特殊的迭代，但是在迭代前不知道还要迭代多少次
递归函数一定有参数，且参数会在迭代的过程中步步逼近某个值
递归函数中一定有处理终点，而这个点就是递归出口
递归
- 有去有回（回到之前的栈帧上）
- 也就是递归这两个字的含义
循环
- 有去无回

分治算法基本思想

分 — 将大规模的原问题分割成 k 个更小规模的子问题，如果子问题的规模仍然不够小，则再划分为 k 个“子子”问题，如此递归地进行下去，直到子问题规模足够小 (基础问题)，很容易求出其解为止。
治 — 求解规模足够小的基础问题。
合 — 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。

分治策略算法细分为三个阶段: Divide 、 Conquer 、 Combine 。 Divide 阶段是把原问题分割成小问题， Conquer 阶段是递归处理流程， Combine 阶段是运用小问题的答案合成出原问题的解答。

分治策略框架程序

(1) if ( | P | <= n0) adhoc(P); //递归出口，用特定程序解决基础问题
(2) divide P into smaller subinstances P1,P2,...,Pk;//分解出子问题
(3) for(i=1,i<=k,i++)
yi = divide-and-conquer(Pi); //递归求解各子问题
(4) return merge(y1,...,yk); //将各子问题的解合并为原问题的解 }

问题规模与递归出口：
- |P|表示问题 P 的规模，𝑛是一个预先定义的阈值，表示当问题 P 的规模不超过𝑛时，问题已容易求解，不必要继续分解和递归调用。
- adhoc(P) 是分治算法中的子程序，对应治过程 (或者说 conquer)，一般是常数时间复杂度的子函数或者子过程。
划分策略：
- 设计划分策略，把原问题 P 分解成 k 个规模较小的子问题，这个步骤是分治算法的基础和关键，人们往往遵循两个原则:
- 平衡子问题原则，分割出的 k 个子问题其规模最好大致相当;
- 独立子问题原则，分割出的 k 个子问题之间重叠越少越好，最好 k 个子问题是相互独立，不存在重叠子问题。
合并：
- merge 合并子程序，把 k 个子问题的解合并得到原问题的解。合并子程序因求解问题而异，即使是同一个问题，如果第二步的划分策略不同，其合并子程序也往往不一样。

减而治之 #

Master 定理 #

e.g.s #

Stirling 数 #

n 个元素的集合{1,2,...,n }可以划分为若干个非空子集的集合。例如，当n=3 时， 集合{1，2，3}可以划分为5个不同的非空子集的集合如下:
{ {1}，{2}，{3} } { {1，2}，{3} }
{ {1，3}，{2} }
{ {2，3}，{1} }
{ {1，2，3} }
给定正整数n 和 m，计算出n个元素的集合{1,2,...,n }可以划分为多少个不同的由 m 个非空子集构成的集合。比如上例中含有1个子集的集合有1个，2个子集的集合有3个， 3个子集的集合有1个。

假定有𝑆(𝑛, 𝑚) 种不同方法把 n 个元素的集合划分成 m 个非空子集构成的集合， 𝑆(𝑛, 𝑚) 种不同划分方法可以分为以下两类:

先把 n-1 个元素的集合划分成 m 个非空子集，按定义其划分数目为 𝑆(𝑛 − 1, 𝑚)，再将剩下的一个元素插入到 m 个子集中的任意一个，最后把这两步合起来则可构成 n 个元素集合的 m 划分，总共有𝑚 ∗ 𝑆(𝑛 − 1, 𝑚) 中划分
先把 n-1 个元素的集合划分成 m-1 个子集，再将剩下的一个元素独立构造成子集，显然，这两步合起来也可以构成有 n 个元素集合的 m 划分，总共有𝑆(𝑛 − 1, 𝑚 − 1) 种划分。

$$𝑆(𝑛, 𝑚) = 𝑚 ∗ 𝑆(𝑛 − 1, 𝑚) + 𝑆(𝑛 − 1, 𝑚 − 1)$$

逆序对问题 #

黑盒划分典型问题

问题描述：设𝐴[1,⋯,𝑛]是一个包含𝑛个不同非负整数的数组。如果在𝑖<𝑗的情况下，有𝐴𝑖>𝐴[𝑗]，则（𝐴𝑖，𝐴[𝑗]）就称为A中的一个逆序对。例如，数组（3，1，4，5，2）的“逆序对”有<3,1>、<3,2>、<4,2>、<5,2>共4个。

思考流程：

朴素方法：枚举
- 将全部的数对枚举出来，检查是否逆序
- 时间复杂度达到指数级别
继续思考：思考方法：降维
- 1 个元素：0 个逆序对
- 2 个元素：比较输出 1/0
- 大于 2 个元素：是否可以将其拆分为 1 个或 2 个元素的情况——分治思路
  - 分——将整体元素分成 2 个部分
  - 治——深入两个部分探究逆序对问题（递归直到归位 base 情况）
  - 合——将处理好的问题合并计数（难点）
    - 分割点左侧全部逆序对
    - 分割点右侧全部逆序对
    - 跨两个集合的逆序对（进一步的真正难点）
      - 朴素方法：枚举——复杂度仍然为指数，没有减少搜索空间
      - 排序——目的：减少比较次数（即搜索空间）
        
        如何比较排序后的数组？左侧数组中从小到大比较右侧数组中的数，O(n) 时间生成逆序总数量
        
        随后使用双指针思路遍历选取即可

棋盘覆盖 #

在一个2k×2k个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格，且称该棋盘为特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。

思考流程：

朴素方法：枚举
- 枚举甚至都无法实现，因为变量太多，且要求不能重叠，导致无法枚举
进阶思考：分治
- 思考方法 - 降维
  - 分解到最基础形态 - 即 2x2 方格
    - 情况 1：方格内存在一个特殊点
      - 直接用 4 种里的一个做匹配即可
    - 情况 2：方格里没有特殊点
      - g 了——有一个空始终无法填满
        
        目标：强制要求每个块内的那个不可覆盖的点组合起来，应该刚好就是 3 个方块组成的元素
        
        把有特殊点的子块当作 indicator，其周围靠近的三个点设为虚拟的特殊点，围绕此展开覆盖，最后覆盖这中间三个特殊点 (或者首先)

void  ChessBoard(int tr, int tc, int dr, int dc, int size)
{
      if (size = = 2) 
           fill(tr, tc, dr, dc);  //覆盖2×2的棋盘
     
       s = size/2;  // 划分棋盘
      
      if (dr < tr + s && dc < tc + s) {  
         ChessBoard(tr, tc, dr, dc, s);  
         //递归处理左上子棋盘
         ChessBoard(tr+s, tc, tr+s, tc+s-1, s);  
         //递归处理左下子棋盘
         ChessBoard(tr, tc+s, tr+s-1, tc+s+1, s);  
         //递归处理右上子棋盘
         ChessBoard(tr+s, tc+s, tr+s+1, tc+s+1, s);  
         //递归处理右下子棋盘
         }
       if (dr < tr + s && dc >= tc + s) { …… } 
       // 特殊方格在右上角子棋盘中
       if (dr >= tr + s && dc < tc + s) { …… } 
       // 特殊方格在左下角子棋盘中
       if (dr >= tr + s && dc >= tc + s) { …… } 
       // 特殊方格在右下角子棋盘中
  }

线性时间选择 #

给定线性序集中n个元素和一个整数 j，1 ≤ j ≤ n，要求找出这n个元素中第 j 小的元素。 例:求数组A[1:9] = [65, 70, 75, 80, 85, 60, 55, 50, 45]第7小元素
partition[1:9]=[60,45,50,55,65,85,80,75,70] j = 7 k = 5 [6:9] = [85,80,75,70] j = 2
partition[6:9]=[70,80,75,85] j = 2 k = 4 [6:8] = [70,80,75] j = 2
partition[6:8]=[70,80,75] j = 2 k = 1 [7:8] = [80,75] j = 1

普通二分查找的问题：最好情况 O(n),最坏情况 O(n^2)

线性时间选择

如果能在线性时间内找到一个划分基准，使得按这个基准所划分出的 2 个子数组的长度都至少为原数组长度的ε倍 (0 < ε < 1)，那么就可以在最坏情况下用 O(n) 时间完成选择任务。
关键问题: 怎样找到一个合适的划分基准元素?

Problem A. 集合划分 #

分治算法典型问题

#### 题目描述

n个元素的集合{1,2,..., n }可以划分为若干个非空子集。例如，当n=4 时，集合{1，2，3，4}可以划分为15 个不同的非空子集如下：

{{1}，{2}，{3}，{4}}，

{{1，2}，{3}，{4}}，

{{1，3}，{2}，{4}}，

{{1，4}，{2}，{3}}，

{{2，3}，{1}，{4}}，

{{2，4}，{1}，{3}}，

{{3，4}，{1}，{2}}，

{{1，2}，{3，4}}，

{{1，3}，{2，4}}，

{{1，4}，{2，3}}，

{{1，2，3}，{4}}，

{{1，2，4}，{3}}，

{{1，3，4}，{2}}，

{{2，3，4}，{1}}，

{{1，2，3，4}}

给定正整数n，计算出n 个元素的集合{1,2,..., n }可以划分为多少个不同的非空子集。

#### 输入数据

多组输入(<=10组数据，读入以EOF结尾) 每组一行输入一个数字，n(0<n<=18)

#### 输出数据

每组输出一行结果。

一种方式是添加元素
一种方式是添加集合

F(n,m)——在有 n 个元素的集合 m 中进行插入

同样目的都是为了插入一个元素——n-1
不同的两种方式
- 向已有集合中添加新元素：m * F(n-1,m)
- 向已有结果中添加新集合：1 * F(n-1,m-1)

Problem B. 二叉树的后序遍历 #

#### 题目描述

给你一个二叉树，按照后序遍历的顺序输出这棵树。

#### 输入数据

第一行一个整数 n (1≤n≤1e4) ，表示这棵树的节点数。 接下来有 n-1 行，每行有两个整数 u,v ，表示节点 u 到节点 v 有一条边，输入保证树以 1 为根，且 u 为 v 的父节点。对于一个节点的多个子节点，将更早输入的那一个子节点的视为他的左子节点。

#### 输出数据

输出该树的后序遍历，节点编号之间用一个空格分隔。

构造树的方法——效果差，代码复杂
直接通过数组对树作快速处理 2

Problem C. 整数的幂次方表示 #

Problem D. 最近点对 #

#### 题目描述

有n个坐标点，问这些点之间最近的一对点的距离是多少？

#### 输入数据

多组输入(<=10组数据，读入以EOF结尾)。 每组第一行输入一个数字，n(1<=n<=100000) 表示坐标点的个数。 随后n行，为两个整数，表示对应的坐标点。

#### 输出数据

每组输出一行结果，保留两位有效数字

Problem E. 小明的散步路径 #

跟之前的方块问题一样，是非常标准非常漂亮的分治算法

Problem F. 气球游戏 #

#### 题目描述

　　刚刚今天去游乐场玩，发现了一个新的游戏项目，游戏是这样的，场上一共有 n 个气球，它们的编号是0到n-1，然后每个气球上还有一个数字，我们使用数组nums来保存这些数字。

　　现在游戏要求刚刚戳破所有的气球。每当刚刚戳破一个气球i时，刚刚可以获得nums[left] * nums[i] * nums[right]个积分。这里的left和right指的是和i相邻的两个气球的序号。（注意每当刚刚戳破了气球i后，气球left和气球right就变成了相邻的气球。）

　　求所能获得积分的最大值。

#### 输入数据

　　输入中有若干组测试样例，第一行为一个正整数T(T≤1000)，表示测试样例组数。每组测试样例包含2部分： 第一部分有一行，包含1个正整数n（0≤n≤500），第二部分为一行，有n个数，第i个数表示num[i],(0≤num[i]≤100)。

#### 输出数据

对每组测试数据，单独输出一行答案，表示最大的积分值