企业官网建设流程全解析

分治算法这个系列写到第四篇，今天不聊排序、不聊归并，来啃一道特别能锻炼递归脑子的题：力扣第241题“为运算表达式设计优先级”。题目很简洁：给你一个由数字和+ - *组成的表达式，返回所有可能的结果，这里的“所有可能”指的是通过不同加括号方式得到的全部计算结果。比如"2-1-1"，既可以算成(2-1)-1 = 0，也可以算成2-(1-1) = 2，所以返回[0, 2]。

这题看起来像是在考“括号的排列组合”，实际上是一个特别典型的分治问题，也是我眼中最适合用来打通“递归直觉”的题目之一。先说我第一次看到它的感受：不是难，是懵。脑子里全是“到底有多少种加括号的方式”“怎么枚举括号位置”这类问题，越想越乱。后来真正想明白之后才发现，核心解法只需要几行递归，而且能自然延伸到区间DP、卡特兰数、构造二叉树等一系列经典话题。这篇文章就把从题目翻译、分治拆解、代码实现到记忆化优化的完整链路讲清楚，顺便把我踩过的几个坑也一并列出来。

1. 为什么“加括号”能考倒一批人——题目拆解与分治思路

1.1 题目到底在问什么

在动手写任何代码之前，先确认题目真正的要求。很多人第一反应是“枚举所有括号”，但题目说得很清楚：返回所有可能的结果。也就是说，我们需要的不是括号本身，而是不同运算顺序下算出来的值。

举个例子，输入"2*3-4*5"。如果完全不考虑加括号，按默认优先级算得到2*3-4*5 = -14。但加上括号之后，顺序可以完全改变：

• (2*(3-(4*5)))得到-34
• (2*((3-4)*5))得到-10
• ((2*3)-(4*5))得到-14
• ((2*(3-4))*5)得到-10
• (((2*3)-4)*5)得到10

所以结果是[-34, -10, -14, -10, 10]。注意这里出现了两个-10，因为不同括号方式可以算出相同的值，题目要求返回所有结果，重复值不需要去重。

这题的精髓在于：表达式里一共有n个数字、m = n-1个运算符，所有合法的加括号方式数量不是阶乘，而是卡特兰数。也就是说，括号结构本身就是一种组合对象，直接枚举会非常痛苦。而分治恰恰能把“括号结构”转化成“选择哪个运算符最后计算”，从而避开对括号形状的显式枚举。

1.2 从暴力枚举到分治：核心观察

先看一个关键事实：任何一个合法的括号化表达式，它的最后一次运算一定是某个运算符。整条表达式可以看作“轴心运算符左侧的表达式”和“轴心运算符右侧的表达式”先算完，最后再把两个结果用轴心运算符合起来。

举例说，如果选择表达式2*3-4*5中的第二个运算符-作为最后计算的运算符，那么左右两侧的表达式分别是2*3和4*5，左边只能算出6，右边只能算出20，最后6-20 = -14。这是五种结果之一。

如果选择的是第一个*作为最后计算的运算符，那么左侧是2，右侧是3-4*5。右侧还能继续加括号，算出不同结果，最终右边结果集合与2做乘法，又会生成新的答案。

这里的关键是：选哪个运算符作为最后计算，就确定了括号结构的“最外层切分”。而左右两侧继续递归选择各自的最后运算符，就自然生成嵌套的括号结构。所以，分治不需要显式拼括号字符串，只需要递归地返回“子表达式所有可能的值”，由外层运算符做笛卡尔积组合。

1.3 关键词：最后一个被计算的运算符

有人会问：那我能不能选“第一个被计算的运算符”作为切分点？逻辑上可以，但选“最后一个”有一个特别大的好处：子问题是干净的表达式子串。

如果选第一个被计算的运算符，左右两侧还需要考虑括号的先后顺序，子问题会退化成“带上下文的表达式”，很不好定义。而选最后一个运算符时，左右两侧完全独立，各自只是原表达式的一个子串，先递归求解子串，再合并即可。这种“切出互相独立的子问题”正是分治的典型特征。

用一个生活类比：把整只鸡炖汤，不同菜谱的区别在于“先炖哪一块、后放哪一块”。分治的思路是先在脑海里挑一个“最后下锅”的部位，把鸡拆成两堆，两堆各自独立炖熟，最后再同一个锅里汇合。至于每一堆内部怎么炖，递归处理就行。这么一想，问题就从“排列组合括号”变成了“不断选择轴心切分”。

2. 分治递归的落地细节与代码实现

2.1 子问题定义与递归出口

先给递归一个清晰的签名：dfs(expr)返回一个列表，表示表达式expr通过任意加括号能得到的所有计算结果。

递归出口很朴素：当expr是纯数字时，不管怎么加括号都只有它本身一个值，直接返回[int(expr)]。注意这里的“纯数字”判断必须是不包含任何运算符，而不是“长度为一”。

接下来是递归展开：从左到右扫描expr，每遇到一个运算符，就把它当作轴心，把字符串切成left = expr[:i]和right = expr[i+1:]。分别调用dfs(left)和dfs(right)，得到左侧所有可能结果和右侧所有可能结果。然后两层循环遍历左右结果，根据轴心运算符做加法、减法或乘法，把所有组合结果收集进res。

为什么这样能覆盖全部情况？因为对任意一种合法的括号化表达式，一定存在一个“最后被计算的运算符”，这个运算符一定来自它的某个中间状态；而当我们的递归扫描到那个运算符时，左右子表达式的所有括号化结果都已经递归生成完毕，合并后一定会把这种结果算进去。

2.2 分割合并：笛卡尔积的写法

合并部分本质上是对两个结果集合做笛卡尔积，再逐对计算。比如左侧结果列表[1, 2]，右侧结果列表[3, 4]，轴心是乘号，那么会生成1*3、1*4、2*3、2*4这四个值。

加法更简单，两侧结果两两相加。减法则要格外注意顺序：一定是left - right，不能反过来。乘法没有顺序问题，只做数值相乘即可。

不要想着用栈去模拟运算顺序，也不需要维护优先级表。分治递归已经天然表达“先算左右、再算轴心”的过程，代码写出来会非常短。

2.3 完整代码与运行演示

直接给一份可以提交的 Python 实现，用functools.lru_cache做记忆化，顺便展示这个解决方案有多简洁：

from functools import lru_cache from typing import List class Solution: def diffWaysToCompute(self, expression: str) -> List[int]: @lru_cache(maxsize=None) def dfs(expr: str) -> List[int]: # 纯数字：直接返回该数字 if expr.isdigit(): return [int(expr)] res = [] for i, ch in enumerate(expr): if ch in "+-*": # 以 ch 为最后运算的运算符，切分左右 left = dfs(expr[:i]) right = dfs(expr[i+1:]) # 笛卡尔积合并 for a in left: for b in right: if ch == "+": res.append(a + b) elif ch == "-": res.append(a - b) else: res.append(a * b) return res return dfs(expression)

我来手动推演一次"2-1-1"的执行过程：

• 第一步，扫描到第一个-，轴心左侧是"2"，右侧是"1-1"。
  • dfs("2")返回[2]
  • dfs("1-1")会先扫到中间的-，左侧"1"返回[1]，右侧"1"返回[1]，合并得到[0]（即1-1）
  • 所以第一次切分得到结果2 - 0 = 2
• 第二步，扫描到第二个-，轴心左侧是"2-1"，右侧是"1"。
  • dfs("2-1")类似返回[1]（即2-1）
  • dfs("1")返回[1]
  • 合并得到1 - 1 = 0

最终结果[2, 0]，符合题目预期。

再看"2*3-4*5"的执行，就能明白为什么结果是五个值。递归会在三种轴心选择上分别展开：选第一个*、选中间的-、选第三个*，每种选择再继续递归，最终收集到[-34, -10, -14, -10, 10]。建议你拿到代码后自己加一行print(expr)跑一遍，亲眼看看递归展开顺序，比看任何讲解都直观。

2.4 多位数处理与解析避坑

示例里的数字都是个位数，很容易让人写出“按字符遍历，遇到单个数字就递归”的错误版本。真实用例里会有"23-1"这种子串。切分时只要按运算符位置切字符串，问题就不存在："23-1"遇到-时，左侧是"23"，右侧是"1"，isdigit()会把"23"整体识别为纯数字，直接返回[23]。

有一个容易忽略的细节：str.isdigit()对负数是返回False的。但题目给定的表达式是合法表达式，数字和运算符交替出现，运算符不会出现在开头，所以不用担心负数子串。如果自己扩展题目、允许负数开头，那就不能单独用isdigit()判断出口了，得先判断首字符是否是负号。不过就这道题而言，原题约束已经足够安全。

另外一个健壮性小问题：递归过程中会不会切出空字符串？合法表达式中，运算符不会出现在两端，所以expr[:i]和expr[i+1:]必然都非空。但如果你手滑写了不合法输入，比如"-1"，那么扫描到-时左侧就是空串，dfs("")会怎样？"".isdigit()为False，它会继续遍历空串，返回[]，合并时没有任何结果，最终返回空列表。为了防止这种情况，可以在dfs开头加一行防御：

if not expr: return []

平时练习时加这一行没坏处，但真正提交时题目保证了合法输入，不加也完全没问题。

3. 复杂度分析、记忆化优化与进阶方向

3.1 不加记忆化会怎样：卡特兰数的直觉

这一题让我特别想聊一下复杂度。很多初学者看到递归代码就会问：这不会是2^n吧？实际上，最终结果的数量对应的是卡特兰数。如果表达式里有n个数字和m = n-1个运算符，那么所有合法加括号方式的数量是第m个卡特兰数：

C_m = (2m)! / ((m+1)! * m!)

当m=3时是5，m=5时是42，m=10时是16796，增长非常迅猛。这就是为什么题目限制了表达式长度不超过20，因为输出数量本身就很大，不限制根本做不了。

如果代码不做记忆化，递归树里同一个子串会被反复求解。比如"2*3-4*5"中，子串"3-4"既可能来自切分2*和3-4*5，也可能来自切分2*3-和4*5后续分支，两条路径都会重新计算它。子问题越多，重复计算越严重。虽然小规模输入可能感觉不出来，但一旦n到十几就会明显变慢。

3.2 记忆化搜索：把重复子问题缓存起来

既然同一个子串会被反复递归，最简单的优化就是缓存。用字典做缓存也是可以的，写出来很直观：

memo = {} def dfs(expr: str) -> List[int]: if expr in memo: return memo[expr] if expr.isdigit(): return [int(expr)] # ... 递归计算 memo[expr] = res return res

用@lru_cache只是把字典缓存包装得更优雅，本质一样。这里有一个实现细节：lru_cache要求函数参数可哈希。字符串天然可哈希，所以直接用expr字符串做缓存键非常合适。但如果有人想传(start, end)索引区间，那参数是整数也可以；而传列表切片结果就不行，会直接报错说 unhashable。

这里还要澄清一个很多人误解的点：记忆化并不会把时间复杂度降成多项式级别。为什么？因为输出结果的数量本身就是卡特兰数，你必须把每一个结果都算出来，这个下界没法突破。记忆化带来的收益是：同一个子串的递归展开只发生一次。举个例子，如果直接从"2*3-4*5"切分到子串"3-4"，第一次需要递归展开"3"和"4"，第二次再从另一条路径进入"3-4"时，直接读缓存，不再重复展开。这让每一层子问题都被复用了，整体运行的常数大幅减小，代码也更优雅。

3.3 从这道题看分治与动态规划的边界

这个题目其实横跨了分治和动态规划两个思想。它的递归划分方式跟归并排序很像，都是把大问题切成小问题，各自求解再合并，这是典型的分治框架。但它又有明显的重叠子问题：同一段子串会被多条递归路径重复访问。一旦叠加记忆化，就成了自顶向下的动态规划，也就是记忆化搜索。

所以我在实际教学中经常用这题作为“分治如何长成 DP”的过渡案例。如果你只习惯写自底向上的区间 DP，也可以把dfs(l, r)改成dp[l][r]数组，枚举区间长度和分割点，本质上和递归是同一套状态转移。

一个额外的话题：如果题目改成“求加括号能得到的最大值”，分治+枚举所有结果再去max就会很傻，因为结果数量是卡特兰数级。正确做法是区间 DP，维护每个子串能得到的最大值和最小值。特别要注意，有乘法时不能只维护最大值，因为负负得正，可能两个很小的负数相乘得到很大的正数。所以要同时维护dp_max[i][j]和dp_min[i][j]，状态转移时把左右两侧的最大、最小互相组合，再分别更新当前区间的最值。这个扩展能帮你把“分治筛选结果”和“区间DP维护状态”的边界看得很清楚，值得自己动手试一次。

3.4 这题还能怎么扩展

除了求最值，还可以做这些变形：

• 把运算符集合从+ - *扩展到/，需要考虑除数为零、整除方向、浮点数精度，难度会明显上升。
• 从“返回所有结果”改成“返回加括号方案的数量”，那答案就是纯卡特兰数，甚至可以一行公式算出来。
• 从“得到所有结果”改成“构造所有可能的加括号树”，那就是二叉树构造类问题，思路跟本题几乎一模一样，只是把结果列表换成树节点列表。

这些方向本质上都在考同一件事：对“最后计算的运算符”这个分治切分点理解得透不透。

4. 实际提交中容易踩的坑与排查技巧

4.1 问题一：递归结果为空导致组合失败

我在调试这道题时，常见的报错现象是：函数最后返回[]，输出为空。原因往往是递归出口写得太“狭窄”。比如有人写：

if len(expr) == 1: return [int(expr)]

如果输入的单数字子串是多位数，例如"23"，长度是2，走不到出口，于是进入循环。但"23"里没有运算符，循环不执行，res保持空列表，最终返回[]。外层合并时，左或右结果为空，整个结果就消失了。

正确出口必须判断“是否包含运算符”，而不是“长度是否为 1”。用isdigit()或者显式检查+ - *是否出现在字符串里都行。记住核心逻辑：没有运算符的子问题，结果就是该数字本身。

4.2 问题二：多位数被拆散

如果直接把expression当成字符数组逐个遍历，遇到数字字符就递归，那么"23+1"会被拆成"2"、"3"、"1"，输出的结果完全不一样。这个问题在示例数据上不容易暴露，因为示例全是个位数。

排查方法很简单：测一次"23-1"，正确输出应该是[22]，如果你拿到的是5之类乱七八糟的值，基本就是多位数处理出了问题。修复思路就是坚持按运算符切分字符串，不要按字符轮询数字。

还有一个隐蔽变体：用expr[0].isdigit()判断是否纯数字。这在"23"上是正确的，但放在"23-1"上也会返回True，因为首字符确实是数字，结果把带运算符的子串错误地直接转成整数23，然后当后续切分到其他分支，数值就会错乱。所以判断必须针对整个子串：要么isdigit()，要么all(ch not in "+-*" for ch in expr)。

4.3 问题三：记忆化缓存 key 选错

用lru_cache时，如果被装饰函数的参数里有不可哈希类型，运行就会报错。有个同学曾把expr转成list传给递归函数，然后用tuple(list_of_chars)做键，绕来绕去把自己绕晕了。最直接的做法就是用原字符串expr做参数，省事又安全。

如果用索引区间[l, r)做递归参数，需要注意区间必须能唯一表示子串内容。原题输入只有一个独立表达式，位置区间天然唯一，所以没问题。但如果你在同一个进程里对不同表达式做多次调用，可能出现不同表达式却有相同(l, r)区间的情况，缓存就会串味。一道题的在线评测不会出现这种跨案例污染，但本地封装工具函数时要注意缓存作用域；建议把dfs定义在Solution方法内部，每次调用独立创建缓存，或者直接用示例代码里嵌套函数的写法，天然隔离。

4.4 调试技巧：打印递归树

递归题调试最忌讳“脑内运行”和“瞎猜”。我通常会在dfs开头加一行打印：

print(f"dfs input: {expr}")

跑一个"2-1-1"就能直观看到递归调用顺序，以及哪些子串被重复调用了。如果你想量化记忆化的收益，还可以维护一个计数器：

counter = {} def dfs(expr): counter[expr] = counter.get(expr, 0) + 1 # ...

开记忆化跑一遍，再看counter里有没有大于 1 的键。如果每个键都只出现一次，说明缓存完全命中；如果出现大量重复，说明lru_cache没生效，八成是参数里有不可哈希类型或者每次传了不同的等价但不等同的字符串表示。

4.5 同类题目速查表

学完这题，敏感度会提高不少，很多题本质上就是“把一个序列切两半，分别求解，再合并”的变体。我把相关的经典题目整理过一张表，初学者按顺序刷会很有用：

刷这些题时，我建议先别急着写代码，拿到题先问自己三个问题：子问题是什么？出口是什么？合并规则是什么？把这三个问题回答清楚，代码基本就出来了。

个人经验是，处理这类“枚举所有顺序”的题目，最忌讳的就是直接上手写复杂数据结构；先画一棵递归树，把"2*3-4*5"的所有切分画完，你对分治的直觉会立刻上一个台阶。而且一定要重视记忆化——哪怕题目数据小到不缓存也能过，但养成“看到重叠子问题就缓存”的习惯，以后做区间DP会顺畅非常多。这题的代码量虽然小，背后藏着的思维量却很大，值得反复咀嚼。