分治算法解题套路框架

本文主要介绍分治算法的核心原理和解题技巧。

分治算法和分治思想这两个概念不太一样，下面通过简单的示例来解释。

分治思想

广义的分治思想是一个宽泛的概念，本站教程中也经常称之为「分解问题的思路」。

分治思想就是把一个问题分解成若干个子问题，然后分别解决这些子问题，最后合并子问题的解得到原问题的解，这种思想广泛存在于递归算法中。

比如斐波那契数列的递归解法，把原问题 fib(n) 分解成 fib(n-1) 和 fib(n-2) 两个子问题，根据子问题的解合并得到原问题的解，这就是分解问题的思路呀：

int fib(int n) {
    // base case
    if (n == 0 || n == 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

普通的二叉树算法，比如让你计算一棵二叉树总共有多少个节点：

// 定义：输入一棵二叉树的根节点，返回这棵树的节点总数
int count(TreeNode root) {
    // base case
    if (root == null) {
        return 0;
    }
    // 先算出左右子树的节点个数
    int leftCount = count(root.left);
    int rightCount = count(root.right);

    // 左右子树的节点个数加上自己，就是整棵树的节点个数
    return leftCount + rightCount + 1;
}

这种解法也是分解问题的思路：你把整棵树的节点个数（原问题）分解成了左子树的节点个数和右子树的节点个数（子问题），然后递归计算左右子树的节点个数，最后根据左右子树的节点个数得到整棵树的节点个数。

再比方说 动态规划算法 属不属于分治思想？

也属于，因为所有动态规划算法都是把大问题分解成了结构相同规模更小的子问题，通过子问题的最优解合并得到原问题的最优解，只不过这个过程中有一些特殊的优化操作罢了。

还可以举出很多例子。其实我在 二叉树心法（纲领篇） 中已经总结过了，递归算法只有两种思路，一种是遍历的思路，另一种是分解问题的思路（分治思想）。

遍历思路的典型代表就是 回溯算法，那么除了回溯算法之外，其他递归算法都可以归为分解问题的思路（分治思想）。

以此观之，「分治思想」占据了递归算法的半壁江山，那么当我们说「分治算法」的时候，具体是指什么呢？是不是可以说上面列举的这些递归算法都是「分治算法」呢？其实不是的。

分治算法

狭义的分治算法也是运用分治思想的递归算法，但它有一个特征，是上面列举的算法所不具备的：

把问题分解后进行求解，相比于不分解直接求解，时间复杂度更低。

符合这个特征的算法，我们才称之为「分治算法」。

上面列举的算法，它们本身就只能分解求解，不存在「直接求解」的解法，所以只说它们运用了分治思想，不说它们是分治算法。

比如 桶排序算法，桶排序的思路是把待排序数组分成若干个桶，然后对每个桶分别进行插入排序，最后把所有有序桶合并，这样时间复杂度能降到 $O(n)$。

直接用 插入排序 的复杂度是 $O(n^2)$，而分解后再用插入排序，总的时间复杂度就能降到 $O(n)$，这种才算分治算法。

那么这里面是什么道理，为什么分而治之的复杂度更低呢？如果把所有问题都分而治之，是不是都能得到更低的复杂度呢？

下面就来详细地对比探究一下，什么情况下分治思想能降低复杂度，什么时候不可以，以及其中的原理所在。