分治算法

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

Theory&Thinkings #

分而治之 #

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

归并排序

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

平衡子问题

减而治之

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

快速归并排序 #enlighten

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


递归三要素:

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

递归与循环

分治算法基本思想

分治策略算法细分为三个阶段: 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); //将各子问题的解合并为原问题的解 }

减而治之 #

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 个非空子集构成的集合, 𝑆(𝑛, 𝑚) 种不同划分方法可以分为以下两类:

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

逆序对问题 #

黑盒划分典型问题

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

思考流程:

棋盘覆盖 #

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

思考流程:

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个点,找其中的一对点,使得在n个点组成的所有点对中,该点对间的距离最小。

思考流程:

线性时间选择 #

给定线性序集中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

线性时间选择

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 中进行插入

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

#### 题目描述

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

#### 输入数据

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

#### 输出数据

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

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)。

#### 输出数据

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

利用递归分治算法的典型:结合必要的备忘录机制用于减少搜索/计算空间