Home
吐槽 源码研究 我的 算法挑战 网络 科学吧 文青 关于我

算法之美第二章

12 May 2014 by LelouchHe

闲话

第一章的习题,终于在时隔一年多之后完结了,回首解题的过程,感觉十分复杂.这一年來发生了很多事情,再加上自己本来就朝三暮四的性格,导致学习的效率十分的低下

现在决定严格的按照顺序來学习,不再东一下西一下的乱搞,搞到最后,每个都烂尾了

接下来的一段时间,会主攻算法之美这本书(话说中文版真的是学计算机的人翻译的么?),争取是一周一章的节奏,包括知识点总结和习题

至于完成之后干什么,目前还没有好的想法,初步的思路是算法导论或算法设计或算法引论三选一,或者全搞,最后搞具体数学做补充

好吧,我一下子就把未来一年都铺垫好了,汗

概述

本章的重点是分治算法,分治是一种非常重要的算法了,如果广义的来看算法分类,基本所有的算法都可以或多或少的算到分治当中.一旦涉及到问题的分类和问题之间的关系构造与维护,基本就会扯上分治

比如下一章的图的分解,看上去貌似只是图这种数据结构自身的操作,但细想,dfs不也是将问题分解为当前节点和相邻节点两个部分,然后分别解决的么?后面的最短路径,贪心/DP等等,莫过如此

但广义角度谈分治,对实际的操作意义不是很大,所以本章还是挑选了一些非常明显和重要的分治应用的例子,让我们了解这种思想

分治的通用步骤

通常,分治分为三个步骤:

  1. 将原问题分解为一组与原问题类型相同的子问题,但每个子问题规模比原问题小
  2. 递归的求解子问题
  3. 将所有子问题的解进行恰当的合并,得到原问题的解

步骤虽简,但如何灵活运用,需要不断的进行总结和练习,现在针对三个步骤,有几个需要特别注意容易忽视的点:

分解

作为分治的第一步,首先需要分析原问题是否存在子问题,这个涉及到边界或者初始值,即后面递归终点的判断.只有原问题确实有子问题,且有必要分解時,我们才开始分解,否则,就需要做为原子问题(不可分),充当递归终点

递归求解第一要素是什么?

从我的经验来看,应该是大多数人都不重视的递归终点.类似归纳法一样,递归终点是归纳/递归的起点,可以是问题无法划分,也可以是问题的规模已经可以求解了.没有递归终点,再怎么递归求解都是假的.所以,这个作为分解的第一步,是非常必要的.主要有以下几个思考的方向:

然后,在分解的过程中,不要拘泥于常见的二分,即将原问题分解为2个子问题.二分并不是分治的全部,子问题的数量和参数的规模往往取决于原问题的状态,很多情况下,二分是合适的(二分简直就是利器,思考无门,尝试二分),但不是全部,目前遇到过的可能的分法有:

在这里罗列这些的目的,并不是让大家遇到问题時一个一个枚举尝试,而是告诉大家,子问题划分的方式是非常多的,也许将来会碰到更复杂,奇怪,甚至恐怖的划分方式,但只要严格分析问题,说明划分的正确性,我们都应该接受.我本人就遇到过类似的情况,一种划分比较罕见,结果就没有勇气分析下去了,但结果证明这种划分是正确的.不要害怕,只要对的,奇怪些无所谓

最后,子问题必须满足的性质是”类型相同,规模减小”:

再多嘴一句,”规模减小”其实也只是形象的说法,减小只是递归解决的常见情况而已,小大都是相互的,只要解决问题就可以,不用拘泥于绝对数量

递归

重点之一依然是上面提到过的递归终点,不过此时,我们对问题有了进一步的了解,通过分解问题,也明确了最后问题会分解成的规模和类型,此时的递归终点探索在于找到这些case,完善递归终点,或者证明这样的东西不存在,推翻分治的基础,从而让我们尝试其他思路

除了迭代的思考递归终点和问题分解之外,递归求解的过程还有一些其他需要思考和迭代的地方:

问题的重新分解,一是大方向的变化,比如以前沿着思路A展开的,在递归求解時发现了矛盾,那么下一次就可以沿着思路B开始;还有更普遍的情况,我们欠缺的只是一两个性质而已,很多情况下,可以通过增加状态或增加维度來解决(想想那么多的DP问题).主要的提醒点在于一旦无法继续,要能想到这两个方向的补救措施,不要茫然失措

合并

合并子问题的难度不定,有的问题合并非常trival,有的则是问题的难点所在(比如平面内最短点对),但此时,与初次遇到问题時相比,我们有几个优势:

当然,这些优势不代表一定可以解决问题,此处只是给各位打一针预防,不要把合并想的非常简单(大部分情况比较简单),合并的复杂度有可能决定了问题的复杂度,不要找不到简单的合并策略,就直接否定了分治的使用,这样是完全错误的

总结

从概述的分析中,可以看到,分治算法的运用,并不是顺序的,而是不停的迭代:

尝试分解 -> 递归表示 + 递归终点 -> 合并 -> 新的分解 -> 新的表示和终点 ->新的合并 …

这样不断的迭代,不断的掌握问题性质,不断的深挖问题本质,才能得到问题的求解.不要寄希望于一蹴而就,相反,如果真的遇到陌生的问题,不停的试错才可能是正常的解决问题之道

分治的理论依据

怎么证明分治的合理呢?其实在我看来,分治的本质就是数学归纳,我们上面讨论的众多情况,其实都在数学归纳法中体现.如果我们数学学的好,见惯众多恶心复杂的利用归纳的问题,那么算法问题其实很微不足道(可惜数学学的一塌糊涂啊..泪奔..)

归纳的关键有2个:

  1. 归纳基础,即我们的归纳终点,一个可以验证,可以直接求解的基础问题.
  2. 递归关系,即我们的分解+递归+合并,三个步骤都会沾一些,这也说明了分治的三步,其实就是一步而已,只不过分割称三个终点不同的子步骤,方便我们focus攻关的重点而已

归纳是一个非常棒的思路,具体的可以参看算法引论,通篇都在讲这一个道理

我们上面提到的各种变化,其实都是数学证明/求解的技巧而已,由于不熟悉,所以才觉得非常神奇.所以说,学好数学,很重要

主定理

求解完分治问题,在估计复杂度時,有一个主定理是非常方便的

假设一个分治问题的递归关系为:

\[\left \\\{ \begin{aligned} T(n) = a T(n / b) + \Theta (f(n)) \\\\ T(0) = O(1) \end{aligned} \right. \Rightarrow T(n) = \left \\\{ \begin{aligned} n ^ {\log _ b a} & \, & n ^ {\log _ b a} = \Omega (f(n)) \\\\ f(n) \log n & \, & n ^ {\log _ b a} = \Theta (f(n)) \\\\ f(n) & \, & n ^ {\log _ b a} = O(f(n)) \end{aligned} \right.\]

可以简单的通过画图得到验证(但估计证明过程肯定也很复杂),我们只需要简单的使用即可.看上去复杂,通用的说法就是看子问题求解($n ^ {\log _ b a}$)和合并($f(n)$)哪个更耗时,如果一样的话,就要加$\log n$即可

整数乘法

我们使用书上的一个例子–整数乘法来熟悉一下整个分治的解题流程

问题

有2个n位的二进制整数x和y,求其乘积

问题的表示

首先尝试使用当前要计算乘积的数对(x, y)来表示问题.其实暂时也想不到更好的方式来表示了,题目中就出现了2个整数

问题的分解

分解问题主要将其规模减小(就本题而言,增大规模貌似没有什么意义),下面我们尝试几种减小规模的思路

单一值减一

将$(x, y)$分解为$(x - 1, y)$,这个看起来也比较合理,然后处理递归终点和合并子问题:

最后分析问题的复杂度,可以直接利用合并公式,$T(x, y) = T(x - 1, y) + O(n)$,得$T(x, y) = O(n) \times O(n) = O(n ^ 2)$.注意,此处的合并复杂度$O(n)$是关于y的位数的,不随着x的变化而变化(因为最后总要与n位的y相加)

这样,我们得到了一个比较简单的整数乘法的算法,复杂度是$O(n ^ 2)$,递归公式如下:

\[(x, y) = \left \\\{ \begin{aligned} 0 & \, & x = 0 \\\\ (x - 1, y) + y& \, & x > 1 \end{aligned} \right.\]

单一值减半

除去减一的方法,我们还可以尝试折半,将某值(比如x)折半,再利用乘法性质组合结果.即将$(x, y)$分解为$(x / 2, y)$,接下来还是递归终点和子问题合并:

\[(x, y) = x y = \left \\\{ \begin{aligned} 2 (x / 2) y = 2 (x / 2, y) & \, & x = 2 k \\\\ 2 (x / 2) y + y = 2 (x / 2, y) + y & \, & x = 2 k + 1 \end{aligned} \right.\]

分析其复杂度,最多减少n次,每次都可能存在$O(n)$的加法运算,所以复杂度是$O(n ^ 2)$,并没有得到很大的改进

对半拆分(存疑)

同样,我们还可以根据某值(比如x)的二进制位来进行拆分成相同位数(n -> n / 2)的两部分,然后分别计算最后的乘积.接下来,还是递归终点和子问题合并:

但这个的时间复杂度一直没有分析清楚,按照我的理解,复杂度是$T(n) = 2 T(n / 2) + O(N + n)$,N是原先y的位数,n是当前x的位数,这样下来总的复杂度是$O(N \log N)$,明显是不对的(普通的乘法应该是$O(n ^ 2)$才对)

全部折半

上面三种方法都是拆分一个值,现在我们尝试分解2个值,以二分为例,令$x = 2 ^ {n / 2} x _ l + x _ r, y = 2 ^ {n / 2} y _ l + y _ r$,然后再相乘求解.接下里分析递归终点和子问题合并:

复杂度分析,$T(n) = 4 T(n / 2) + O(n) = O(n ^ 2)$,还是普通的乘法操作

优化

可以利用乘法性质,对这种分解进行优化,其实这个还算容易看得出来,4次乘法是多余的,因为中间的$(x _ l, y _ r) + (x _ r, y _ l)$其实没必要单独计算,只要计算其和就可以了,利用公式$(x _ l + x _ r) (y _ l + y _ r) = x _ l y _ l + x _ r y _ r + (x _ l y _ r + x _ r y _ l) \Rightarrow x _ l y _ r + x _ r y _ l = (x _ l + x _ r) (y _ l + y _ r) - (x _ l x _ r + y _ l y _ r)$,利用原先必须计算的两个独立乘积,和1个新的乘积,就可以完成原先的4个乘积了

现在的复杂度是$T(n) = 3 T(n / 2) + O(n) = T(n ^ {\log _ 2 3})$,比平方复杂度优化了不少

排序

还是利用经典的问题,来审视分治的流程

问题

n个元素的无序数组,设计算法将其变成有序

问题的表示

涉及到数组的问题,一般的常见表示有两种:

  1. 数量表示 使用(n)来表示,这种情况一般是处理和个数相关的问题,与数组元素的位置没有关系
  2. 范围表示 使用(l, r)来表示,这种表示包含了个数(r - l + 1),同时包含了位置,对于位置相关的问题,可以采用类似的表示

当然,这只是常见的情况,在分析问题时遇到其他情况,也要接受

问题的分解

下面我们使用上面的2种表示,逐一进行问题分解,考察如何在不同表示下分解/迭代问题

减一

当使用(n)表达问题時,通过减一來减小问题规模,就是将(n)分解为(n - 1).什么时候n个数的排序可以变为n - 1个数的排序呢?自然是知道了某个数的确切位置時.其中,最简单的情况应该就是最大值和最小值了.下面看下递归终点和子问题合并:

这种算法的复杂度是$T(n) = O(n) + T(n - 1) + O(1)$(从前往后分别是挑选最大值,子问题和子问题合并的复杂度),计算可知,最后$T(n) = O(n ^ 2)$.这种排序是经典的选择排序.

进一步

除了最大值和最小值,我们还可以尝试其他的值么?那是肯定的.最大/最小只不过是一种”选择”的方式,自可以选择其他的值v,首先确定v的位置,然后处理剩下的n - 1个数的排序.

比如我们决定按顺序考虑,每次考虑数组的首个元素,设为v.怎样才能得到v的位置呢?自然的思路是排序了,不过这就绕回原问题了,所以不能这样做(鸡生蛋,蛋生鸡啊).仔细思考下,通过排序决定位置,包含了很多不需要的数据,比如根本不需要除了v之外的其他值的相对顺序,找到比v小的值的数量,即可确定v的位置了.

沿着”找到比v小的值的数量”这个思路,就有一个简单的算法來完成,遍历整个数组,统计比v小的数量,这样就得到了v的位置(假设为k).好的,我们完成了问题分解,问题确实变成了小问题(n -> n - 1),接着看看递归终点和子问题合并:

我们就又成功解决了问题,复杂度是$T(n) = O(n) + T(n - 1) + O(n)$(分别是查找位置k,子问题,插入位置k),最后得到$T(n) = O(n ^ 2)$

可以看大,相比最大/最小值,随机选取一个值的复杂度类似,但实现上,觉得甚是不爽,比如插入v的时候,需要移动$O(n)$的数组,这个是否可以避免呢?既然我们知道v的位置是k,为什么不一开始就放到k去,非要最后再插入呢?

所以我们换一种分解问题的思路,还是选择首个元素v,找到位置k,然后把v和原k位置的$v ‘$互换,这样v就到了一个固定不变的位置,只要不动v,就不会影响其排序结果.但现在,原问题变成了分割的2个部分,[0, k)和[k + 1, n),个数分别是k和n - k - 1,都小于n,这样问题的规模减小了,让我们看下递归终点和子问题合并:

此时复杂度为$T(n) = O(n) + T(k) + T(n - k - 1) + O(n), k \in [0, n)$,平均下来,$T(n) = O(n \log n)$

再进一步,最后的合并还是好麻烦,还需要跳过k(好反人类啊),有什么办法不需要k搀和么?自然的想法就是如果前后两个分割的序列是独立的就好了,即[0, k)所有的元素都小于[k + 1, n),这样二者排序之后,原序列就自然有序了,不需要merge或者跳过k了.怎么做到这点呢?在前面统计小于v的个数時,我们会遍历所有的元素,有小有大,小的必然是在[0, k),大的必然在[k + 1, n)(虽然只有最后才知道k的大小),既然此时有了这个信息,就可以利用这个來做划分,小于的放到”小于数组”里,大于的放到”大于数组”里,这样就成功拆分了.接下来看递归终点和子问题合并:

这样的复杂度比原先少了合并的$O(n)$,但总的复杂度依然是$O(n \log n)$

变换表示

随着”进一步”的分析,问题越来越和位置相关了,那么就來看下如果利用位置相关的(l, r)怎么处理最后一种情况

原问题是处理(0, n - 1)的无序序列,按照最后一种的思路,其实就是将其划分为(0, k - 1)和(k + 1, n - 1)两个子问题.再看下递归终点和子问题合并:

此时,复杂度是$T(l, r) = O(n) + T(l, k - 1) + T(k + 1, r)$,平均下来,依然是$O(n \log n)$

可以看到,此时的合并操作非常简洁,直接得到了问题的解.

为什么会这样呢?

因为我们在问题表达上自带了位置信息.上一种表达((n))只有数量,没有位置,导致的结果就是在合并時需要手动指定.其实可以看得出来,对于排序而言,位置是一个重要的信息,不在问题表示中体现,就需要在问题表示之外人工体现(比如合并時).排序本身就是位置和值的重新映射,位置自然是必要信息

折半

考虑过”减一”分解之后,再來看看传统的”折半”,即将问题(n)分解为(n / 2)來考察,得到2个有序序列之后,然后解决原序列的排序.我们看下递归终点和子问题合并:

这样,复杂度是$T(n) = 2 T(n / 2) + O(n) = O(n \log n)$

这样的方法很类似与上面减一的方法,唯一不同的是我们没有挑选元素v的位置k來完成问题的分解,而是直接简单粗暴的一分为二了.

总结

可以看到,分治的大体步骤是:

  1. 分析问题表达,将问题参数化(有可能的话适当泛化),使问题的规模可度量
  2. 尝试分解问题,将问题规模减小(或者增大)
  3. 分析该分解下的递归终点和子问题合并,能否正确得到原问题结论
  4. 3中出现错误時,返回1,更新问题的表达,补充证明中缺失的信息

分解问题的方法还有很多,从不同角度,不同维度分析问题,肯定都能得到很多不同的分解方法.此处主要是为了提醒大家注意以下几点:

FFT

FFT的数学原理没有看懂,但背后的解题思路还是可以借鉴一下的,此处不讨论数学,只讨论解题

铺垫

多项式有两种等价的表达方式,系数表达($\sum a _ i x ^ i$)和值对表达($(x _ i, A(x _ i))$).其中,n次多项式需要n+1个不同的值对來唯一确定

在处理多项式相乘時,如果采用值对表达的方式,复杂度是$O(n)$(只需要将二多项式在对应$x _ i$处的值相乘即可),而系数表达的话,复杂度是$O(n ^ 2)$.

如果能找到一种快速的变换方式(复杂度不高于$O(n ^ 2)$),那么整个多项式乘法就可以以小于$O(n ^ 2)$來计算了.

此处的FFT(快速傅立叶变换)就是完成这样工作的,它的复杂度是$O(n \log n)$,所以最后的多项式乘法复杂度就是$O(n \log n)$

问题

有多项式$A(x) = \sum ^ n a _ i x ^ i$,求2n个值对$(x _ i, A(x _ i)), x _ i \neq x _ j$,$x _ i$需要解题者自己提供

ps:反正就是要2n个不同的值对就行,至于是哪些值对,问题本身不关心,也就是说我们可以随意自取

注意,这是一个很强的可以利用的性质,问题不关心我们选取了哪些$x _ i$,只要有2n个不同的$x _ i$和对应的$A(x _ i)$,就完成了我们的任务

问题的表达

问题中有n个值要进行计算,每个都是n次方的多项式值,所以一个合理的表示是将这两部分都加入问题表达,即(m, n),其中m表示需要求值的数量,n表示多项式的次数.那么原问题是(2n, n).

这只是初步的预计,后续可以迭代的进行修改

其实我们完全可以直接根据公式来计算这n个值.直接计算一个n次多项式的值的复杂度是$O(n)$(假设x很小,基本运算是单位时间),那么2n个值的复杂度为$O(n ^ 2)$.有这样的复杂度,和直接计算多项式乘法复杂度相同了,所以这个应该是我们寻求算法的上限

问题的分解

依据上一个问题的思路,尝试各种减小问题规模的方法

求值数量减一

将(m, n)分解为(m - 1, n)感觉是个不错的开始,多项式次数不变,但求值的个数减一.接下来我们看下递归终点和子问题合并:

子问题合并并不是一个非常直观的过程,所以单独展开来说

子问题合并

现在的问题是我们有了前m-1个值对$(x _ i, A(x _ i))$,如何求得第m个值对.

由于可以随意选择这m个数,我们可以选择$x _ m = s$(随意的某个特定取值而已),这样就能在$O(n)$的复杂度下计算$A(x _ m)$.但这样的算法和直接计算没有任何区别,并没有利用到已经解决的子问题,所以不可取

那么此时的目标是利用子问题来求解,也就是说$x _ m$不能使随意的特定值,相反,$x _ m = f(x _ 0, x _ 1, \dots, x _ {m - 1})$,从而使得$A(x _ m) = g(A(x _ 0), A(x _ 1), \dots, A(x _ {m - 1}))$.同时,这样的性质可以延续到子问题中(才能保证问题类型相同)

从简单入手,假如已知$A(x _ 0)$,如何挑选合适的$x _ 1$,从而得到$A(x _ 1)$呢?仔细想想,其实没有很好的办法,都只能选择一个$x _ 1$,然后按照$O(n)$来直接计算$A(x _ 1)$.

为什么?

因为目前只有$(x _ 0, A(x _ 0))$两个独立且没有太大关系的值,虽然我们知道$A(x)$多项式的表达,但是却没有在这里体现出来,也就无法复用在$x _ 1$的求解中了.回想下整数乘法中的优化,是如何利用3次乘法得到4个需要的乘积项的.

这告诉我们一个原则,整体往往容易掩盖部分,比如$x y$和$A(x)$,掩盖了其中可以重复利用的细节,而这些重复,往往是优化的关键步骤.如果有个名称的话,这应该是上面说的”充分利用信息”.此处我们就要剖析这种细节

假设$A(x)$为3次多项式,则有$A(x) = \sum a _ i x ^ i = a _ 0 + a _ 1 x + a _ 2 x ^ 2 + a _ 3 x ^ 3$,怎么拆开可以利用的细节呢?

尝试前后拆分,即$A _ {prev} = a _ 0 + a _ 1 x, A _ {post} = a _ 2 x ^ 2 + a _ 3 x ^ 3 = x ^ 2 (a _ 2 + a _ 3 x)$(时刻不忘向相似方向努力!!).一个好的现象是多项式次数降低了($n \Rightarrow n / 2$),但由于$A _ {prev}, A _ {post}$之间没有可重复利用的,需要求解的值反而翻倍了($m \Rightarrow 2 m$),所以肯定不会改善复杂度的

其实可以想到,不论怎么拆分,多项式次数肯定会减小的(不要太奇葩,我们要找相似),关键在于如何减少需要求解的值,或至少维持不变.

我们再次尝试,来按奇偶拆分,即$A _ e (x) = a _ 0 + a _ 2 x ^ 2, A _ o (x) = a _ 1 x + a _ 3 x ^ 3 = x (a _ 1 + a _ 3 x ^ 2)$,看到了整齐划一的平方项,应该能想到平方根的性质$x ^ 2 = (- x) ^ 2$,这样在处理相反数时,我们有了可以利用的项了,即$A _ e (x ^ 2) = a _ 0 + a _ 1 x, A _ o (x ^ 2) = a _ 1 + a _ 3 x \Rightarrow A (x) = A _ e (x ^ 2) + x A _ o (x ^ 2), A(- x) = A _ e (x ^ 2) - x A _ o (x ^ 2)$,求解的值数量不变,但次数降低了,由$(m, n)$变换为了$(m, n / 2)$,问题的规模减少了

走到这里,感觉貌似减一的分解测试是不行的.我们还不容易找到的子问题合并方法,要求的是多项式次数折半,看来是时候需要改变分解策略了

多项式次数折半

此时,$(m, n)$分解为$(m, n / 2)$,再来讨论递归终点和子问题合并

不知道各位看到问题了没有,虽然我们解决了$A(x)$和$A(- x)$,但是$A _ e (x ^ 2)$和$A _ o (x ^ 2)$怎么办?此处已经不能随意选择x的值了,只能利用这个$x ^ 2$,但$x ^ 2$怎么区分正负呢?只好进入复数域了,此时有$j ^ 2 = -1$(j为单位虚数).这样就又可以一正一负的挑选了.

那最初究竟挑选哪些值呢?1次方多项式的话,只需要一个数即可,比如s,那么有它组成的2次方多项式对应的取值,则是其平方根$\pm \sqrt {s}$,4次方多项式对应的就是$\pm \sqrt [4] {s}, \pm \sqrt [4] {s} j$,依次类推.但我们总共有2n个不同的值,如果s是任意的数,我们最后会有$O(2 ^ n)$个初始$x _ i$,所以需要让这些值也是重复的,令$s = 1$就可以解决这个问题了,此时的$x _ i = w ^ i$,其中w是1的n次方根,$w ^ n = 1 \Rightarrow w = e ^ {\frac{2 \pi}{n} j}$

下面我们用伪码来描述整个过程:

fft(A, w) {
    if (w == 1) {
        return A(1);
    }

    A(x) = Ae(x^2) + x * Ao(x^2);
    Ve = fft(Ae, w^2);
    Vo = fft(Ao, w^2);
    for (int i = 0; i < n; i++) {
        V(i) = A(w^i) = Ae(w^2i) + w^i * Ao(w^2i);
    }

    return V;
}

总结

其实我还应该带着大家探索下有没有别的分治的方法来解决FFT问题,但此处我们先总结下上面流程的一些要点:

关于多样性

这里我想多说一句,同后面可能的DP的讨论类似,在考虑子问题合并时,自然的想法是哪些子问题可以合并为原问题,就好像站在某点,思考哪些点是可以”跳过来”的.

还有一种思考方式是,站在某点,想可以”跳去”哪里

这两个思路是不一致的,前者往往是综合的,如同本章分析的所有问题一样,是得到完整的原问题解的过程,而后者是局部的,即子问题可能前进到多个父问题,但每个父问题都是部分解决.(给人的感觉很像MST的prim和kruskal,前者每一时候都是当前问题的解,但后者每一时候只是解的一部分)

两种思考方向都是可以的,只不过有的时候一种比另一种更容易罢了.像本章所述的几个问题,都是按照”跳过来”的方式思考的,因为子问题数量和种类有限,思考不是很复杂.但对于其他的问题,可能返回来想更容易(比如在DP中,复杂的状态转移就不容易”跳过来”,相反,”跳去”是相对容易的),我们就可以先反向的思考,得到所有的复杂的转移方式,然后再统一处理合并的问题

此处还是要强调”分割步骤”的重要性,有些时候,每个步骤都非常复杂,必须分割,否则混合起来越想越乱,最后只能不了了之了

写在最后

理解分治的本质就是归纳,而归纳是解决一大类问题的方法,基本可以运用到所有的题目上去

分治不一定只要得到求解的具体算法,这也是深入了解问题性质的一个思考方向,没准在思考过程中,就柳暗花明也说不定

后面会结合本章的习题,细细的品味分治的妙处