算法思想（一）：分治、回溯

递归

递归，去的过程叫“递”，回的过程叫“归”。能够用递归解决的问题都需要满足如下几个条件：

• 存在递归终止条件
• 一个问题可以分解为多个子问题
• 问题和子问题，除了处了的数据规模不同，解决思路完全相同

我们需要找到将大问题分解为小问题的规律，并且基于此写抽象成一个递推公式，这个过程要注意，不要试图用人脑去分解递归的每个步骤，只要考虑当前层的逻辑。

使用递归还要注意重复计算问题，可以使用字典表缓存已经计算的结果。比方说爬楼梯问题暴力递归的时间复杂度是 O(2^n) ，在使用缓存之后时间复杂度就是 O(n)。

/**
 * 递归代码模板
 **/
public void recur(int level, int param) {
    // 终结者 
    if (level > MAX_LEVEL) {
        // process result
        return; 
    }

    // 当前层逻辑
    process(level, param);

    // 下一层
    recur(level + 1, newParam);

    // 重置当前状态
}

分治

分治就是“分而治之”，将原问题划分成 n 个规模较小而结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。用分治思想解决问题需要具有如下条件：

• 原问题与分解成的小问题具有相同的模式

• 原问题分解成的子问题可以独立求解，子问题之间没有相关性不会相互影响

• 具有分解终止条件，也就是说，当问题足够小时，可以直接求解

• 可以将子问题合并成原问题，但合并操作的复杂度不能太高，否则算法总体复杂度无法减小分

分治思想的代码包括 3 个步骤，分解、解决、合并：

• 分解：将原问题分解为一系列子问题

• 解决：递归地求解各个子问题，若子问题足够小，则直接求解

• 合并：将子问题的结果合并成原问题的解

/**
 * 分治代码模板
 * 求多数元素
 **/
private int majorityElementRec(int[] nums, int low, int high) {
    // Step1: 最小子问题, 可直接得出结果, 也是递归终止条件
    // 这里就是将数组分解成只有一个元素
    if (low == high) {
        return nums[low];
    }

    // Step2: 准备数据
    // 这里将数据一切为二
    int mid = (high - low) / 2 + low;

    // Step3: 问题分解并求出子问题
    // 这里是分别求出左多数和右多数
    int left = majorityElementRec(nums, low, mid);
    int right = majorityElementRec(nums, mid + 1, high);

    // Step4: 合并结果, 得出最终结果
    // 这里是返回左右两边数量最多的数
    if (left == right) {
        return left;
    }
    int leftCount = countInRange(nums, left, low, high);
    int rightCount = countInRange(nums, right, low, high);
    return leftCount > rightCount ? left : right;
  
    // Step5: 恢复状态
}

回溯

回溯就是采用试错的思想，从一组可能的解中，选择出一个满足要求的解。

• 穷举所有的解，找到满足要求的解
  • 通过将问题分解为多个阶段（步骤），来穷举所有的可能解
  • 通过尝试发现当前的阶段的答案不能得到正确的解，将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的解
• 利用剪枝操作，排除不需要穷举的情况，从而提高效率

总结

递归是解决问题一种手段属于编程技巧，而分治、回溯、贪心算法、动态规划属于算法思想。他们的关键是都是要找到问题的重复性。

分治思想的核心就是分而治之。在工程实践中 MapRedue 的本质就是分治，比方说 Spark 解决单机节点性能问题，将任务拆分到多个机器上处理，子任务之间互不干扰独立计算，最后再将合并结果。

回溯相当于穷举所有的情况，然后对比得到最优解。回溯算法的时间复杂度非常高，是指数级别。可以利用剪枝操作，排除不需要的分支，从而提高效率。

本周的算法思想并不难理解，关键是解决问题的时候能够找出问题的重复性，并且能够分解出子问题。“思想”总是高度抽象，想要灵活运用还是要多多练习这类的题目。