Algorithm Design and Analysis: Divide and Conquer, Dynamic Programming, and Graph Algorithms

Introduction

算法是怎么被想出来的？算法设计出来的规则是很好理解的，但是其他人是究竟怎么想出来这样的解答的。为什么我们自己想不出来这样的处理方式。

我们需要想到一个处理问题的思路，希望能够通用化的设计这样的思路，用一套思想来分析问题，而不是依靠灵光一现。

科学研究的基本思路

首先，我们将遇到一个实际的问题，选择或者发现一个实际的问题
下一步，我们希望能够把实际问题变成一个算法问题或者数学问题
最后，我们来处理这个问题

处理数学问题的基本思路

尝试从正面来处理这个问题
如果正面无法处理这个问题，或许考虑这个问题根本无法处理

Way1

这个问题中最简单的一个case能不能被处理？
1. 当最简单的问题都不能被处理的时候，放弃即可
2. 当最简单的问题可以被处理的时候，去处理他
当简单的case能够被处理，但复杂的不行，那复杂的case可以被分解为简单的case吗，也就是decompose可行吗？当分解可行，那归纳法就是可行的
当分解可行，且原始问题是优化问题，并且原始问题的最优解可以用小问题的最优解组合出来，那么就可以采取动态规划
当前面的条件都满足，并且最优解可以被local的看到，那么就可以采取贪心

Way2 当问题不可以被分解，而是需要研究解之间的变换，那就可以考虑另一类算法，比如线性规划，网络流等方法

Way3 当都不可行，而是需要去研究枚举，那么就可以去考虑有没有更好的枚举策略，整个分支系列算法都是这么处理的

Last Way 最后，有没有similar的问题，尝试similar问题的算法

AI时代的算法设计，在初始的算法设计中，会有很多随机尝试的方法，在AI时代，这种随机尝试或许可以使用神经网络与大量预先收集到数据来进行固化，这种方法有时候可以增加运算的效率。即使用NN替换原本非常复杂的模块

分治（Divide Conquer）

基本思想：现实世界中有很多问题都是递归的，大问题和小问题之间唯一的区别就是大小。要解决大问题，我们可以将其分解为小的问题，通过递归调用处理小的问题，就可以组合出原始问题的解。

Divide 分解得到小问题
Conquer 处理小问题（程序上的递归）
Combine 得到大问题的解

Divide与Combine的核心就在于如何观察输出与输出的数据结构形式，他决定了我们如何划分和合并，我们不妨研究常见的数据结构，并研究他们如何分与合，数组，矩阵，集合，树，图是最常用的数据结构

对于一个数组，每个元素都有两个属性：值与下标；

那么我们很容易得到一个基本的基于下标的划分，将其中一个元素拿出来，分成两个数组，分别有 $n$ 个与 $n-1$ 个元素。然后对于较大的组重复划分，直到最简单的我们会处理的两个元素的形式，最后一步步重新合并。对应于排序任务，这就是插入排序。

再换一种划分方式，从中间划分成基本差不多大的序列，然后重复划分。最后合并的时候应该分别从两组开始，选择其中最小的元素。而两个已经排序好的组，最小的元素一定在最左侧，从最左侧开始比较，每次都能挑走最小的元素，就可以减少排序的消耗。这是归并排序。

再想一种划分方式，我们考虑从数组的值身上考虑划分；随机挑选一个pivot元，将比其大的元素作为A组，比他小的元素作为B组，然后分别对这两个组进行递归的调用排序函数，直到所有元素都被正确排序，现在无需要combine，就是一个排序好的序列了，重新组合即可，这就是快速排序。

这样的思路还可以用在很多问题上，如果我们想找到 $A$ 个元素中第 $k$ 大的，我们也可以使用类似快排的方法，按照值划分。随机选择一个pivot，将比其大的元素作为A组，比他小的元素作为B组，然后写逻辑判断第k大的元素在哪一个组里，再递归调用这样的函数。最后返回那个找到的元素。

对于图数据，这种在算法题中也比较常出现的数据，我们可以考虑通过减少顶点与边的方式实现divide，也是要从最简单的情况开始考虑并分析

对于矩阵的divide，很自然的，我们会希望根据位置将矩阵分块，直到变成小块比较容易处理。在高速的矩阵乘法（或者更多的矩阵相关问题上）中就使用了这样的divide思路。事实上，大数乘法也是在使用这样的divide思路

想要让divide conquer加速，最核心的两个思路在于

让需要被直接递归计算的分块变少，即使用分块的加性处理新的分块
将一次分块得到的分块更小，小分块有利于更少的时间复杂度

如果一个可以divide的问题是一个优化问题，并且可以用子问题的解合成大问题的解，我们就要考虑使用动态规划了，这是divide conquer的进一步思考。后面的greedy贪心也会是动态规划的一种改进。

动态规划（Dynamic Programming）

DP基础

动态规划处理的问题依旧是需要可分的问题，只不过这里我们希望介绍更多的将问题变成可分问题的思路，这就是本节希望学会的——使用DP的思想思考并处理各种问题的方法。

如果我们的核心问题是寻找最优决策，并且问题可以被建模为一个多步的决策过程，就可以考虑使用DP

我们先引入一个基本的例子：有三架飞机，10枚导弹，每个飞机都有自己在各个导弹数量下的击落概率以及自身的价值，如何优化实现最高的总击落价值。

枚举对于更大规模是不现实的，但是对于这种涉及纯整数的问题，我们可以考虑使用多步决策的方法（因为纯整数意味着可选的决策有限）将问题进行另一种特殊的divide

定义：函数 $max{V(x,y)}$ 为在 $y$ 个导弹下，摧毁 $x$ 个飞机能够得到的最大价值

那么此时我们希望计算 $max{V(3,10)}$ ，我们实际上是在决策每个飞机需要使用多少个导弹，因此我们可以首先先进行第一步决策，直接枚举第一架飞机的情况，那么 $maxV(3,10)=max\{max(2,x)+EV(x)\}$ 即使用了 $10-x$ 个飞机攻击第一架飞机得到的期望价值以及另一个迭代调用的 $maxV$ 函数。

通过递归调用这样的计算程序，就可以将问题简化为一架飞机的情况，最终完成求解。因为这个模型的最简单形式，一架飞机与任何数量的导弹，都是容易被处理的问题（正如我们在开篇提到的，从简单开始）

这样的多步决策与优化总价值的思路就是Bellman方程最初的起源，如果问题可以被概括为多步决策并且最优解之间有递归关系，这样的求解思路就是可行的。

理解多步决策处理问题的思路，将涉及决策的问题建模为多步决策的结构，通过一步一步的优化来实现求解复杂的问题。每一步决策的选择本身应该是简单的，不应该具有过多的分支，决策后产生结果以及后面进一步递归的进行决策应该尽量容易用代码实现，不要产生大量的if分支

前面介绍的多步决策实际上都是递归列举的思路，多层的递归调用并且全部计算都会产生很多性能的开销，我们需要考虑一些减少多步决策开销的方法。dp在实际的使用上的时候存储子问题的结果，当子问题需要被再一次解决的时候，就可以直接查表，降低最终的复杂度。

三个经典的DP

矩阵运算最少次数：有一个矩阵乘积的序列，共 $A_1,...,A_n$ 共 $n$ 个矩阵，大小分别为 $p_0,...p_n$ 用什么样的运算顺序，可以得到最少的总运算次数，注：大小分别为 $p_0,p_1;p_1,p_2$ 的矩阵相乘运算的总次数为 $p_0p_1p_2$

这样的一个问题可以很自然的化为多步决策的情况，我们需要决策让哪些矩阵先乘起来。而如何把这个长的矩阵乘积序列变成类似问题的短矩阵，只需要增加括号，增加一个最后再乘积的断点。

定义： $OPT(i,j)$ 是 $i,j$ 上矩阵乘积的最小运算次数（对于这种类字符串的问题，哪怕是单串，但还是习惯使用两个位置跟踪，如回文数，有效括号长度），那么可以自然的给出一个迭代公式

OPT(i,j)=min\{OPT(i,k)+OPT(k+1,j)+p_{i-1}p_kp_j\}

使用这样的递归公式就可以把最长序列一路降维的两个矩阵乘积的情况

字符串匹配程度：给出两个字符串 OCCURCE,OCUORCE 判断这两个字符串的匹配情况，当对应位置完美匹配则加一分，匹配错误或遗漏则扣三分，计算最大的匹配分数。

这是两个较长的字符串序列，太长的字符串我们不好处理，因此我们希望还是减少长度，很简单的思想就是从末尾开始逐个减少，因此选择 $OPT(i,j)$ 表示对于字串1到 $i$ 处，子串2到 $j$ 处，两个字串匹配的程度。

对于两个字串的最后一个字符有三种可能的匹配情况，分别是 $E-E;E-NULL;NULL-E$ 那么可以给出 $OPT$ 的一种决策迭代形式有

OPT(i,j)=max~\begin{aligned} &s(i,j)+OPT(i-1,j-1)\\ &s(i,NULL)+OPT(i-1,j)\\ &s(NULL,j)+OPT(i,j-1)\end{aligned}

这实际上就是在决策最后一个元素的匹配情况，然后将长字符串变成更多的字符串，从而让这里定义的OPT实现了迭代。

最长公共子序列：给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

我们还是有两个串需要追踪，过长的字符串难以处理，因此我们还是希望递归的减少字符串长度，还是从尾部追踪字符串，定义 $OPT(i,j)$ 为字串1 $i$ 之前与字串2 $j$ 之前的最长公共子序列，通过决策最后一个位置的匹配程度，可以给出迭代有

OPT(i,j)= \begin{aligned} &0~~if~~ i=j\\ &OPT(i-1,j-1)+1 ~~if~~T[i]=T[j]\\ &max\{OPT(i-1,j),OPT(i,j-1)~~if~~T[i]\ne T[j]\}\end{aligned}

dp中的递归处理问题的思路并不要求我们一定要递归的使用用于生成提问结果的函数，我们自己定义新的函数，这个函数用于生成一些过渡性的结果。

这种OPT函数定义出来是为了可以通过递归的使用他们来将问题简化为最简单的形式（我们可以直接处理的形式），这种递归实际上就是通过一步的决策，将问题复杂度降低了。

定义新的OPT函数

最长回文：给你一个字符串 s，找到 s 中最长的回文子串。“bab” 是一个长度为3的回文子串。

很自然的，对于长度为1 我们知道他一定满足回文，为了缩减长度（此时一定不是从头部或者尾部缩减，而是对称的进行回文的缩减），建立OPT函数，我们不应该建立 $OPT(i,j)$ 表示这个区间内最长的回文字符串长度，而是用他判断这个区间的字符串是否回文，那么可以给出递归有

OPT(i,j)= OPT(i+1,j-1) ~~if ~~s[i]==s[j]

当 $j-i==1$ 或者 $j-i==2$ 的时候，不在考虑子串。

最长有效括号：你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

可以考虑使用单串追踪，研究以 i 结束的最长有效括号长度。这样是可以建立递归的；也可以考虑使用两个指标追踪，研究区间内的括号是否有效，递归可以通过消除最后一个括号建立（最后一个括号一定是’)’才合法）

数组上的DP

很多处理数组的问题，他们没有显式的决策，但是我们希望讨论的最简单问题是短数组而真实问题是长数组，我们实际上就是要建立递归的方程（bellman方程）将数组的长度变短。建立新的opt函数，真实问题的解隐藏在这个opt函数里，然后研究如何递归的处理这个opt函数。

能够建立的opt函数应该是多种多样的，当处理困难的时候及时变换设计这个opt函数的思路也很重要。多步决策方法大概率是不唯一的，因此在使用dp的时候，也要灵活的调整思路，使用不同的方法来将大问题变小。

决策的目的是把复杂问题变简单，而数组本身天然存在长度这个因素决定了问题的复杂程度，因此这种动态规划的核心就在于找到缩短长度的子问题，找到复杂度越来越低之间的问题的递归。寻找长度越来越短的opt函数之间的递归关系。而数组的缩短也很简单，无非是按照顺序从前/从后开始减少长度。

综上，处理数组的时候找不到决策并不可怕，往往处理数组反而更简单，其思路更加的固定且死板。

最长上升子序列：给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。

对于只有一两个元素的数组，这个问题很好处理，但是长起来就没那么好处理了，因此我们需要考虑使用DP的方法来降低数组的长度。对于这种单串的数组，最好的决策方法就是从数组头或者尾部建立缩减长度的OPT函数。

因此定义 $OPT(i)$ 为恰好到第 $i$ 个元素，数组的最长上升子序列。综上就可以给出递推为

OPT(n)=OPT(n-1)+1 ~~if~~ num[n]>num[n-1]

这里使用的是恰好到第i个元素，而非初始问题的到第i个元素其中的，就是为了更容易给出这种递归关系，我们在前面介绍字符串的使用也进行了这样的自定义，最后对所有 $OPT[i]$ 进行一次max即可

最大子序和：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

还是数组的问题，很自然的简单情况容易处理，复杂情况不好处理，我们希望减少数组长度来把复杂变得简单。定义 $OPT(i)$ 是恰好以第 i 个数结尾的连续子数组的最大和，自然的给出递推

OPT(i) = max(OPT(i-1)+num[i],num[i])

和上一个小问题一样，我们建立的是恰好以第 i 个数结尾，因为这样递归形式更容易构造处理。

可能陷入循环的DP

有向无环图经过一次拓扑排序后就是一个数组；他上面的最短路问题就可以理解为一个多步决策的过程，倒序和顺序均可。

当上面存在环的时候，最短路问题就会出现循环依赖性，不断递归的死循环调用，这种情况一定是需要处理的。此时最常用的方法就是增加一个递归函数的参数，让他在递归调用的时候不断减小。实际上就是增加解的结构的粒度，让问题更细。实际上这种让问题更细的思路和前面的构造新的opt的思想是一样的。构造合适的OPT就是核心

贪心（Greedy）

Greedy 思想

在动态规划里面，我们在某个位置的时候不知道此时的最优决策是什么，因此需要递归的计算全部情况才可以知道最后的结果。而有时候，我们在局部就知道最优决策是什么，因此我们就可以介绍Greedy

选课问题：给定 $N$ 门课程，每个课程都有对应的上课时间与下课时间以及上课人数 $W_i$ ，如何排课使得课程补充，并且上课人数最大化

大问题不好求解，但是子结构（只有1-2门课）容易通过几个if判断，也是一个优化问题，那么动态规划大概率可以很好的处理这个问题。排课问题在某种程度上也可以看成数组，缩短长度就是求解的核心，不妨倒着从下课开始考虑使得我们可以少追踪一些信息，定义 $OPT(S,T)$ 是在 $T$ 时刻之间时间可用，仍有 $S$ 门课程可以被排课的最大上课人数，倒序一门一门课取消

OPT(S,T)=max\{OPT(S-课x-冲突课,课x的上课时间)+W_x,OPT(S-课x,T) \}

通过多步决策最后一门课上不上，就可以递归的遍历全部情况最后得到大问题的解，之所以从最后一门课开始减少仅仅是为了减少设计 $OPT$ 的难度。

当所有的 $W_i$ 为1的时候，我们就可以使用Greedy处理这个问题，只需要不断的选择最早下课的课程/最晚上课的课程，同步的去除冲突的课程，就可以找到最优解，与此同时无须进行对所有情况递归的遍历。我们无需求解子问题，而是选择局部的最优

动态规划和Greedy非常的相似，他们都主要用于处理优化问题且基于子结构分析，所有的Greedy背后都有一个对应的DP，去枚举所有情况而不是选择局部最优，他们都能够处理这样的问题

还是前面的排课问题，我们到底应该Greedy的进行什么样的决策？靠自己的Idea去选择合适的方案大概率是出错的，比如先安排上课最早的课程/先安排时间最短的课，而找到前面的贪心策略并不是一个非常容易的事情。

去尝试的寻找贪心的规则，再去思考规则的合理性，不能完全依赖从DP的得到Greedy，而是要自主的尝试Greedy规则，再去思考和验证合理性，不断的试错，我们后面再介绍一些思考细节

Greedy理论

Greedy方法用来处理下面的问题，给定一个集合 $S$ ，找到他的一个子集 $A$ ，让 $F(A)$ 最大。在没有贪心方法的时候，我们只能去遍历整个集合找到所有可能的子集。当然，Greedy只能处理这一类问题中的两种情况

$f(S)=\sum w_i$ 这就是说，每个子元素对整个函数值的情况无关
$f(x)$ 不是线性的函数，但是他是凸的，此时可以找到近似最优解

问题1:寻找向量组的极大无关组，此时每个向量都有自己的价值，我们希望最大化最后极大无关组的价值。

这很自然的可以概括为多步决策，利用DP算法处理问题，通过迭代的从尾部决策是否加入最后一个向量，就可以处理问题（类似于排课问题）。

但是此时，我们希望最大化价值函数对于各个子集都是线性的，那么我们就可以考虑贪心策略，不断引入价值最高的向量直到不满足无关组。

Prim算法，Kruskal算法，Dijkstra算法也使用了贪心的策略，因为他们整体的距离也是一个线性函数，寻找最小生成树与最短路径都是寻找子集，因此Greedy策略就是可行的，以后遇到类似的问题也可以考虑Greedy，而非使用多步决策的DP

我们前面还介绍了一类可以考虑Greedy的情况，由于此时考虑的是集合函数，当他满足下面的性质的时候，可以考虑Greedy

f(A)+f(B)\ge f(A\cup B)+f(A\cap B)

等价定义

if~S_{1}\subset S_{2} ~then~f(S_{1}+e)-f(S_{1})\ge f(S_2+e)-f(S_2)

也就是一种近似单调性，起码子集扩大函数值不会变小。

这个定义体现了一种近似凸的性质，在现在的子集较小的时候，增加的元素会让整体函数值增加较快，当子集较大的时候，函数值的增加就没有那么明显了，增量和基础相关

为什么这个东西有用？因为他可以提供一个上界，令 $S\subset T,T-S=E$ 并且 $e_i$ 是 $E$ 中所有元素则有

f(T)\le f(S)+\sum e_i

遇到这种函数应该采取什么样的贪心策略？去找最大新增，也就是边际增量最大的情况。这样决策以后，增量会越来越小，我们最后找到的解，会是近似最优的情况。如果遇到类似的问题（如背包问题），也可以考虑近似的贪心策略，寻找性价比最高的元素。找到一个值得贪心的指标，然后执行贪心，至于为什么可以考虑这样的贪心，因为这些问题都类似于铺砖的问题，最后的价值集合函数具有一种上凸性