CHARLIE SAYS

分治算法的基本思想是将一个规模为 N 的问题分解为 K 个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。下面通过典型题目来理解分治思想。

给表达式加括号

241. Different Ways to Add Parentheses (Medium)

Input: "2-1-1".
((2-1)-1) = 0
(2-(1-1)) = 2
Output : [0, 2]

对表达式遍历，每遇到一个运算符，就把表达式拆成左右两个子表达式，分别递归求出各自的所有可能结果，再把左右结果按该运算符两两组合——子问题相互独立且与原问题性质相同，正是典型的分治。

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;
}

系列导航

• 上一篇：算法思想：贪心算法
• 下一篇：算法思想：回溯算法
• 相关篇：算法思想：二分法（二分查找是分治思想的典型应用）、算法思想：动态规划算法（与分治的区别在于保存子问题的解避免重复计算）