分治算法详解：运算优先级

241. 为运算表达式设计优先级 https://leetcode.cn/problems/different-ways-to-add-parentheses

241. Different Ways to Add Parentheses https://leetcode.com/problems/different-ways-to-add-parentheses

Info

已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	力扣	难度
241. Different Ways to Add Parentheses	241. 为运算表达式设计优先级	🟠

在 手把手带你刷二叉树（纲领篇） 中，我说递归算法主要有两种思路，一种是「遍历」的思路，另一种是「分解问题」的思路。我说「遍历」思路的典型代表是回溯算法，「分解问题」思路的典型代表是动态规划。

之所以说动态规划是「分解问题」思路典型代表，主要还是因为大家比较熟悉这类算法。但实际上，很多算法问题不具备动态规划问题的重叠子问题、最优子结构等特性，但都可以用「分解问题」的思路来解决，我们可以给这些算法一个高大上的名字，统称为「分治算法」。

最典型的分治算法就是 归并排序 了，核心逻辑如下：

void sort(int[] nums, int lo, int hi) {
    int mid = (lo + hi) / 2;
    // ****** 分 ******
    // 对数组的两部分分别排序
    sort(nums, lo, mid);
    sort(nums, mid + 1, hi);
    // ****** 治 ******
    // 合并两个排好序的子数组
    merge(nums, lo, mid, hi);
}

「对数组排序」是一个可以运用分治思想的算法问题，只要我先把数组的左半部分排序，再把右半部分排序，最后把两部分合并，不就是对整个数组排序了吗？

下面来看一道具体的算法题。

添加括号的所有方式

我来借力扣第 241 题「为运算表达式设计优先级」来讲讲什么是分治算法，先看看题目：

241. 为运算表达式设计优先级 | 力扣 | LeetCode |

给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。

生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 104 。

示例 1：

输入：expression = "2-1-1"
输出：[0,2]
解释：
((2-1)-1) = 0 
(2-(1-1)) = 2

示例 2：

输入：expression = "2*3-4*5"
输出：[-34,-14,-10,-10,10]
解释：
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10

提示：

• 1 <= expression.length <= 20
• expression 由数字和算符 '+'、'-' 和 '*' 组成。
• 输入表达式中的所有整数值在范围 [0, 99] 

简单说，就是给你输入一个算式，你可以给它随意加括号，请你穷举出所有可能的加括号方式，并计算出对应的结果。

函数签名如下：

java 🟢

// 计算所有加括号的结果
List<Integer> diffWaysToCompute(String input);

cpp 🤖

// 计算所有加括号的结果
std::vector<int> diffWaysToCompute(std::string input);

python 🤖

# 计算所有加括号的结果
def diffWaysToCompute(input: str) -> List[int]:

go 🤖

// 计算所有加括号的结果
func diffWaysToCompute(input string) []int {
    // your code here
}

javascript 🤖

// 计算所有加括号的结果
var diffWaysToCompute = function(input) {

};

看到这道题的第一感觉肯定是复杂，我要穷举出所有可能的加括号方式，是不是还要考虑括号的合法性？是不是还要考虑计算的优先级？

是的，这些都要考虑，但是不需要我们来考虑。利用分治思想和递归函数，算法会帮我们考虑一切细节，也许这就是算法的魅力吧，哈哈哈。

废话不多说，解决本题的关键有两点：

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

这一点我们前文经常提及，比如 手把手刷二叉树第一期 就告诉你解决二叉树系列问题只要思考每个节点需要做什么，而不要思考整棵树需要做什么。

说白了，解决递归相关的算法问题，就是一个化整为零的过程，你必须瞄准一个小的突破口，然后把问题拆解，大而化小，利用递归函数来解决。

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

这也是前文经常提到的一个点，因为递归函数要自己调用自己，你必须搞清楚函数到底能干嘛，才能正确进行递归调用。

下面来具体解释下这两个关键点怎么理解。

我们先举个例子，比如我给你输入这样一个算式：

1 + 2 * 3 - 4 * 5

请问，这个算式有几种加括号的方式？请在一秒之内回答我。

估计你回答不出来，因为括号可以嵌套，要穷举出来肯定得费点功夫。

不过呢，嵌套这个事情吧，我们人类来看是很头疼的，但对于算法来说嵌套括号不要太简单，一次递归就可以嵌套一层，一次搞不定大不了多递归几次。

所以，作为写算法的人类，我们只需要思考，如果不让括号嵌套（即只加一层括号），有几种加括号的方式？

还是上面的例子，显然我们有四种加括号方式：

(1) + (2 * 3 - 4 * 5)

(1 + 2) * (3 - 4 * 5)

(1 + 2 * 3) - (4 * 5)

(1 + 2 * 3 - 4) * (5)

发现规律了么？其实就是按照运算符进行分割，给每个运算符的左右两部分加括号，这就是之前说的第一个关键点，不要考虑整体，而是聚焦每个运算符。

现在单独说上面的第三种情况：

(1 + 2 * 3) - (4 * 5)

我们用减号 - 作为分隔，把原算式分解成两个算式 1 + 2 * 3 和 4 * 5。

分治分治，分而治之，这一步就是把原问题进行了「分」，我们现在要开始「治」了。

1 + 2 * 3 可以有两种加括号的方式，分别是：

(1) + (2 * 3) = 7

(1 + 2) * (3) = 9

或者我们可以写成这种形式：

1 + 2 * 3 = [9, 7]

而 4 * 5 当然只有一种加括号方式，就是 4 * 5 = [20]。

然后呢，你能不能通过上述结果推导出 (1 + 2 * 3) - (4 * 5) 有几种加括号方式，或者说有几种不同的结果？

显然，可以推导出来 (1 + 2 * 3) - (4 * 5) 有两种结果，分别是：

9 - 20 = -11

7 - 20 = -13

那你可能要问了， 1 + 2 * 3 = [9, 7] 的结果是我们自己看出来的，如何让算法计算出来这个结果呢？

这个简单啊，再回头看下题目给出的函数签名：

java 🟢

// 定义：计算算式 input 所有可能的运算结果
List<Integer> diffWaysToCompute(String input);

cpp 🤖

// 定义：计算算式 input 所有可能的运算结果
vector<int> diffWaysToCompute(string input);

python 🤖

# 定义：计算算式 input 所有可能的运算结果
def diffWaysToCompute(input: str) -> List[int]:

go 🤖

// 定义：计算算式 input 所有可能的运算结果
func diffWaysToCompute(input string) []int {}

javascript 🤖

// 定义：计算算式 input 所有可能的运算结果
var diffWaysToCompute = function(input) {
    // function body here
};

这个函数不就是干这个事儿的吗？这就是我们之前说的第二个关键点，明确函数的定义，相信并且利用这个函数定义。

你甭管这个函数怎么做到的，你相信它能做到，然后用就行了，最后它就真的能做到了。

那么，对于 (1 + 2 * 3) - (4 * 5) 这个例子，我们的计算逻辑其实就是这段代码：

java 🟢

List<Integer> diffWaysToCompute("(1 + 2 * 3) - (4 * 5)") {
    List<Integer> res = new LinkedList<>();
    // ****** 分 ******
    List<Integer> left = diffWaysToCompute("1 + 2 * 3");
    List<Integer> right = diffWaysToCompute("4 * 5");
    // ****** 治 ******
    for (int a : left)
        for (int b : right)
            res.add(a - b);

    return res;
}

cpp 🤖

vector<int> diffWaysToCompute("1 + 2 * 3 - 4 * 5") {
    vector<int> res;
    // ****** 分 ******
    vector<int> left = diffWaysToCompute("1 + 2 * 3");
    vector<int> right = diffWaysToCompute("4 * 5");
    // ****** 治 ******
    for (int a : left)
        for (int b : right)
            res.push_back(a - b);

    return res;
}

python 🤖

def diffWaysToCompute("(1 + 2 * 3) - (4 * 5)"):
    res = []
    # ****** 分 ******
    left = self.diffWaysToCompute("1 + 2 * 3")
    right = self.diffWaysToCompute("4 * 5")
    # ****** 治 ******
    for a in left:
        for b in right:
            res.append(a - b)
        
    return res

go 🤖

func diffWaysToCompute("(1 + 2 * 3) - (4 * 5)") []int {
    res := []int{}
    // ****** 分 ******
    left := diffWaysToCompute("1 + 2 * 3")
    right := diffWaysToCompute("4 * 5")
    // ****** 治 ******
    for _, a := range left {
        for _, b := range right {
            res = append(res, a - b)
        }
    }

    return res
}

javascript 🤖

var diffWaysToCompute = function("(1 + 2 * 3) - (4 * 5)") {
    var res = [];
    // ****** 分 ******
    var left = diffWaysToCompute("1 + 2 * 3");
    var right = diffWaysToCompute("4 * 5");
    // ****** 治 ******
    for (var a of left)
        for(var b of right)
            res.push(a - b);

    return res;
}

diffWaysToCompute("(1 + 2 * 3) - (4 * 5)");

好，现在 (1 + 2 * 3) - (4 * 5) 这个例子是如何计算的，你应该完全理解了吧，那么回来看我们的原始问题。

原问题 1 + 2 * 3 - 4 * 5 是不是只有 (1 + 2 * 3) - (4 * 5) 这一种情况？是不是只能从减号 - 进行分割？

不是，每个运算符都可以把原问题分割成两个子问题，刚才已经列出了所有可能的分割方式：

(1) + (2 * 3 - 4 * 5)

(1 + 2) * (3 - 4 * 5)

(1 + 2 * 3) - (4 * 5)

(1 + 2 * 3 - 4) * (5)

所以，我们需要穷举上述的每一种情况，可以进一步细化一下解法代码：

java 🟢

class Solution {
    public List<Integer> diffWaysToCompute(String 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));
        }
        return res;
    }
}

cpp 🤖

class Solution {
public:
    vector<int> diffWaysToCompute(string input) {
        vector<int> res; 
        for (int i = 0; i < input.size(); i++) {
            char c = input[i];
            // 扫描算式 input 中的运算符
            if (c == '-' || c == '*' || c == '+') {
                // ****** 分 ******
                // 以运算符为中心，分割成两个字符串，分别递归计算
                vector<int> left = diffWaysToCompute(input.substr(0, i)); 
                vector<int> right = diffWaysToCompute(input.substr(i + 1));
                // ****** 治 ******
                // 通过子问题的结果，合成原问题的结果
                for (int a : left)
                    for (int b : right)
                        if (c == '+')
                            res.push_back(a + b);
                        else if (c == '-')
                            res.push_back(a - b);
                        else if (c == '*')
                            res.push_back(a * b);
            }
        }
        // base case
        // 如果 res 为空，说明算式是一个数字，没有运算符
        if (res.empty()) {
            res.push_back(stoi(input));
        }
        return res;
    }
};

python 🤖

class Solution(object):
    def diffWaysToCompute(self, input):
        res = []
        for i in range(len(input)):  
            c = input[i]  
            # 扫描算式 input 中的运算符
            if c in ['-', '*', '+']:  
                # ****** 分 ******
                # 以运算符为中心，分割成两个字符串，分别递归计算
                left = self.diffWaysToCompute(input[:i])  
                right = self.diffWaysToCompute(input[i+1:])  
                # ****** 治 ******
                # 通过子问题的结果，合成原问题的结果
                for a in left:  
                    for b in right:  
                        if c == '+':  
                            res.append(a + b)
                        elif c == '-':
                            res.append(a - b)  
                        elif c == '*':
                            res.append(a * b)
        # base case
        # 如果 res 为空，说明算式是一个数字，没有运算符
        if not res:
            res.append(int(input))
        return res

go 🤖

func diffWaysToCompute(input string) []int {
    res := []int{}
    for i := 0; i < len(input); i++ {
        c := input[i]
        // 扫描算式 input 中的运算符
        if c == '-' || c == '*' || c == '+' {
            // ****** 分 ******
            // 以运算符为中心，分割成两个字符串，分别递归计算
            left := diffWaysToCompute(input[:i])
            right := diffWaysToCompute(input[i+1:])
            // ****** 治 ******
            // 通过子问题的结果，合成原问题的结果
            for _, a := range left {
                for _, b := range right {
                    if c == '+' {
                        res = append(res, a+b)
                    } else if c == '-' {
                        res = append(res, a-b)
                    } else if c == '*' {
                        res = append(res, a*b)
                    }
                }
            }
        }
    }
    // base case
    // 如果 res 为空，说明算式是一个数字，没有运算符
    if len(res) == 0 {
        num, _ := strconv.Atoi(input)
        res = append(res, num)
    }
    return res
}

javascript 🤖

var diffWaysToCompute = function(input) {
    let res = [];
    for (let i = 0; i < input.length; i++) {
        let c = input.charAt(i);
        // 扫描算式 input 中的运算符
        if (c == '-' || c == '*' || c == '+') {
            // ****** 分 ******
            // 以运算符为中心，分割成两个字符串，分别递归计算
            let left = diffWaysToCompute(input.substring(0, i));
            let right = diffWaysToCompute(input.substring(i + 1));
            // ****** 治 ******
            // 通过子问题的结果，合成原问题的结果
            for (let a of left)
                for (let b of right)
                    if (c == '+')
                        res.push(a + b);
                    else if (c == '-')
                        res.push(a - b);
                    else if (c == '*')
                        res.push(a * b);
        }
    }
    // base case
    // 如果 res 为空，说明算式是一个数字，没有运算符
    if (res.length == 0) {
        res.push(parseInt(input));
    }
    return res;
};

有了刚才的铺垫，这段代码应该很好理解了吧，就是扫描输入的算式 input，每当遇到运算符就进行分割，递归计算出结果后，根据运算符来合并结果。

这就是典型的分治思路，先「分」后「治」，先按照运算符将原问题拆解成多个子问题，然后通过子问题的结果来合成原问题的结果。

当然，一个重点在这段代码：

java 🟢

// base case
// 如果 res 为空，说明算式是一个数字，没有运算符
if (res.isEmpty()) {
    res.add(Integer.parseInt(input));
}

cpp 🤖

// base case
// 如果res为空，说明算式是一个数字，没有运算符
if (res.empty()) {
    res.push_back(stoi(input));
}

python 🤖

# base case
# 如果 res 为空，说明算式是一个数字，没有运算符
def numDistinct(s: str, t: str) -> int:
    if not res:
        res.append(int(input))

go 🤖

// base case
// 如果 res 为空，说明算式是一个数字，没有运算符
if len(res) == 0 {
    i, _ := strconv.Atoi(input)
    res = append(res, i)
}

javascript 🤖

// base case
// 如果 res 为空，说明算式是一个数字，没有运算符
if (res.length == 0) {
    res.push(parseInt(input));
}

递归函数必须有个 base case 用来结束递归，其实这段代码就是我们分治算法的 base case，代表着你「分」到什么时候可以开始「治」。

我们是按照运算符进行「分」的，一直这么分下去，什么时候是个头？显然，当算式中不存在运算符的时候就可以结束了。

那为什么以 res.isEmpty() 作为判断条件？因为当算式中不存在运算符的时候，就不会触发 if 语句，也就不会给 res 中添加任何元素。

至此，这道题的解法代码就写出来了，但是时间复杂度是多少呢？

如果单看代码，真的很难通过 for 循环的次数看出复杂度是多少，所以我们需要改变思路，本题在求所有可能的计算结果，不就相当于在求算式 input 的所有合法括号组合吗？

那么，对于一个算式，有多少种合法的括号组合呢？这就是著名的「卡特兰数」了，最终结果是一个组合数，推导过程稍有些复杂，我这里就不写了，有兴趣的读者可以自行搜索了解一下。

其实本题还有一个小的优化，可以进行递归剪枝，减少一些重复计算，比如说输入的算式如下：

1 + 1 + 1 + 1 + 1

那么按照算法逻辑，按照运算符进行分割，一定存在下面两种分割情况：

(1 + 1) + (1 + 1 + 1)

(1 + 1 + 1) + (1 + 1)

算法会依次递归每一种情况，其实就是冗余计算嘛，所以我们可以对解法代码稍作修改，加一个备忘录来避免这种重复计算：

java 🟢

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

    public 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++) {
            // ...
        }
        if (res.isEmpty()) {
            res.add(Integer.parseInt(input));
        }
        // ***********************

        // 将结果添加进备忘录
        memo.put(input, res);
        return res;
    }
}

cpp 🤖

class Solution {
public:
    // 备忘录
    unordered_map<string, vector<int>> memo;

    vector<int> diffWaysToCompute(string input) {
        // 避免重复计算
        if (memo.count(input)) {
            return memo[input];
        }
        // ****** 其他都不变 ******
        vector<int> res;
        for (int i = 0; i < input.length(); i++) {
            // ...
        }
        if (res.empty()) {
            res.push_back(stoi(input));
        }
        // ***********************
        
        // 将结果添加进备忘录
        memo[input] = res;
        return res;
    }
};

python 🤖

class Solution:
    # 备忘录
    memo = {}

    def diffWaysToCompute(self, input: str) -> List[int]:
        # 避免重复计算
        if input in self.memo:
            return self.memo[input]
        # ****** 其他都不变 ******
        res = []
        for i in range(len(input)):
            # ...
        if not res:
            res.append(int(input))
        # ***********************
        
        # 将结果添加进备忘录
        self.memo[input] = res
        return res

go 🤖

// 备忘录
var memo = make(map[string][]int)

func diffWaysToCompute(input string) []int {
    // 避免重复计算
    if val, ok := memo[input]; ok {
            return val
    }
    // ****** 其他都不变 ******
    var res []int
    for i := 0; i < len(input); i++ {
        // ...
    }
    if len(res) == 0 {
        num, _ := strconv.Atoi(input)
        res = append(res, num)
    }
    // ***********************

    // 将结果添加进备忘录
    memo[input] = res
    return res
}

javascript 🤖

var Solution = function() {
    // 备忘录
    this.memo = {};
};

Solution.prototype.diffWaysToCompute = function(input) {
    // 避免重复计算
    if (this.memo.hasOwnProperty(input)) {
        return this.memo[input];
    }
    // ****** 其他都不变 ******
    var res = [];
    for (var i = 0; i < input.length; i++) {
        // ...
    }
    if (res.length === 0) {
        res.push(parseInt(input));
    }
    // ***********************

    // 将结果添加进备忘录
    this.memo[input] = res;
    return res;
}

这个优化没有产生复杂度上的改变，只是对一些特殊情况做了剪枝，提升了运行效率。