分治算法--表达式的不同优先级

添加括号的所有方式

给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 *

递归的要点:

1、不要思考整体，而是把目光聚焦局部，只看一个运算符

2、明确递归函数的定义是什么，相信并且利用好函数的定义。

// 备忘录
HashMap<String, List<Integer>> memo = new HashMap<>();

List<Integer> diffWaysToCompute(String input) {
  	// 避免重复计算
    if (memo.containsKey(input)) {
        return memo.get(input);
    }
  
    List<Integer> res = new LinkedList<>();
    for (int i = 0; i < input.length(); i++) {
        char c = input.charAt(i);
        // 扫描算式 input 中的运算符
        if (c == '-' || c == '*' || c == '+') {
            /****** 分 ******/
            // 以运算符为中心，分割成两个字符串，分别递归计算
            List<Integer> 
                left = diffWaysToCompute(input.substring(0, i));
            List<Integer> 
                right = diffWaysToCompute(input.substring(i + 1));
            /****** 治 ******/
            // 通过子问题的结果，合成原问题的结果
            for (int a : left)
                for (int b : right)
                    if (c == '+')
                        res.add(a + b);
                    else if (c == '-')
                        res.add(a - b);
                    else if (c == '*')
                        res.add(a * b);
        }
    }
    // base case
    // 如果 res 为空，说明算式是一个数字，没有运算符
    if (res.isEmpty()) {
        res.add(Integer.parseInt(input));
    }
  	// 将结果添加进备忘录
    memo.put(input, res);
    return res;
}

总结

解决上述算法题利用了分治思想，以每个运算符作为分割点，把复杂问题分解成小的子问题，递归求解子问题，然后再通过子问题的结果计算出原问题的结果。