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

labuladong原创约 2753 字

本文讲解的例题

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 位整数范围，不同结果的数量不超过 10⁴ 。

示例 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) {

};

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

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

添加括号的所有方式