论“任何问题都是分治”这一观点

· · 个人记录

分治是一切算法之源,任何算法本质上都是分治。

显然,无论是正常的分治算法还是递归递推,甚至是 dp 和 A+B 这种基础的算法本质上都是分治思想。

接下来以一个例子来说明,并得出普遍结论以证明以上观点:

动态规划之类的问题

众所周知,动态规划会有一个数组被称为 dp 数组,有很显然,dp 数组一定是由前几个状态转移而来,若我们用递归来实现,我们就能显然的发现当前的状态被分成了若干个可以转移到它的状态,这不就是一个分治的过程吗?

完备性证明

证明如下:

分析一个代码,我们能够发现,代码的运行是有顺序,那么我们就可以看成把一个复杂的问题,分解成了一段一段的代码,也就是一个一个小的问题来分段解决。这就是分治的思想。

综上,证毕。