3.3 分治算法

基本定义

分治算法（Divide and Conquer）是一种解决问题的算法范式，它将一个大问题分解成多个小问题，然后分别解决这些小问题，最后将它们的解合并起来得到原始问题的解。分治算法通常包含三个步骤：

1. 分解（Divide）： 将原始问题分解成规模较小的子问题，通常是相同或相似的问题。这个步骤要求将问题划分成互相独立的子问题，以便并行地解决它们。
2. 解决（Conquer）： 递归地解决每个子问题。如果子问题足够小，无需再次进行分解，而可以直接求解。
3. 合并（Combine）： 将子问题的解合并成原始问题的解。这个步骤通常涉及将多个子问题的解组合起来，得到原始问题的解。

分治算法通常用于解决那些具有重叠子问题和最优子结构性质的问题。重叠子问题意味着原始问题的解可以通过解决相同的子问题来获得。最优子结构意味着原始问题的最优解可以通过其子问题的最优解来计算。分治算法的经典应用包括归并排序（Merge Sort）、快速排序（Quick Sort）、求解最近点对问题、求解最大子数组问题等。这些问题都可以通过分解成小的子问题，递归地求解这些子问题，最后合并子问题的解来获得原始问题的解。

基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。

案例

https://leetcode.cn/problems/different-ways-to-add-parentheses/description/

public List<Integer> diffWaysToCompute(String input) {
    List<Integer> ways = new ArrayList<>();
    for (int i = 0; i < input.length(); i++) {
        char c = input.charAt(i);
        if (c == '+' || c == '-' || c == '*') {
            List<Integer> left = diffWaysToCompute(input.substring(0, i));
            List<Integer> right = diffWaysToCompute(input.substring(i + 1));
            for (int l : left) {
                for (int r : right) {
                    switch (c) {
                        case '+':
                            ways.add(l + r);
                            break;
                        case '-':
                            ways.add(l - r);
                            break;
                        case '*':
                            ways.add(l * r);
                            break;
                    }
                }
            }
        }
    }
    if (ways.size() == 0) {
        ways.add(Integer.valueOf(input));
    }
    return ways;
}