Python|分治（分而治之）法

前言

分治思想自古就有，在《孙子兵法》中有这么一句话：凡治众如治寡，分数是也：斗众如斗寡，形名是也。

问题描述

今天我们讲的是分治法，首先来了解一下分治法的定义：把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并，这就是分治法。

解决方案

简单来说，分治法的基本思想就是：把一个大的问题分解成若干个小问题，求出若干个小问题的解并将其合并，得到的就是大问题的解。但是，并不是所有的问题都可以用分治法来解决，从它的基本思想我们就可以看出，能用分治法解决的问题一定具有以下特征：
①.该问题可以分解为若干个规模较小的相同问题
注意几个关键词：“可以分解”，“规模较小”，“相同问题”。如果说我们分解之后不是相同的问题而是其他的问题，那么你只是把一个问题分解成了若干个问题，这样你真的可以获得若干份的快乐吗？
②.该问题的规模缩小到一定的程度就可以容易地解决；
我们把大问题分解成小问题，目的就是问题缩小后可以轻易地解决，如果连着一点都不能满足，那么，何必呢？针对这一条特征我们就可以看出来，分治法和递归其实是分不开的。因为第一次把大问题分解成小问题的时候，不一定就可以解决，需要再把小问题分解成小小问题，小小问题分解成小小小问题，不断分解的过程就是一个递归的过程
③.分解后的子问题的解可以合并为该问题的解
这一步很关键，它决定了我们是否可以使用分治法去解决问题。
④.该问题所分解出的各个子问题是相互独立，即子问题之间不包含公共的子问题。

就是说子问题之间不包含公共的子问题，如果包含了公共的子问题，那么求出的解就有部分是重复的，合并之后的解肯定是不正确的。

结语

我们简单介绍了分治法，通过以上讲解我们可以看到分治和递归宛如一对孪生兄弟，有分治法的地方就有递归的身影。因此要想运用好分治法一定要先理解运用好递归，遇到问题方能分而治之，逐个击破。

作者：唐雷清

实习编辑：衡辉

稿件来源：深度学习与文旅应用实验室（DLETA）