最近整理自己的刷题笔记时第 101 条记录停留在“Different Ways to Add Parentheses为运算表达式设计优先级”这道题上。第一次看到2*3-4*5的样例输出时我盯着那五个结果愣了好一会儿同一个式子只是括号位置不同结果从 -34 到 10 全都能算出来。这根本不是传统意义上的“运算符优先级”而是一道典型的“枚举所有运算树”问题。这篇笔记我会按自己实际的复盘顺序来写先拆题面再说为什么别从穷举括号入手然后给出分治递归的完整实现最后重点聊聊记忆化优化、复杂度真相以及几个我实际踩过的坑。适合刚接触分治递归、或者刷了很多题但对“加括号类问题”始终有点模糊的读者。1. 题面拆解同一条表达式为什么能算出多个结果1.1 先把所有括号方式手算一遍题目给的输入是一个由数字和、-、*三种运算符组成的字符串输出是所有可能的结果顺序可以任意。比如2-1-1只有两种加括号方式((2-1)-1) 0(2-(1-1)) 2所以返回[0, 2]。再看复杂一点的2*3-4*5它的五种加括号方式可以写成下面这张表加括号方式计算过程结果(2*(3-(4*5)))2 * (3 - 20)-34((2*3)-(4*5))6 - 20-14((2*(3-4))*5)(2 * (-1)) * 5-10(2*((3-4)*5))2 * (-5)-10(((2*3)-4)*5)(6 - 4) * 510这里有个非常容易忽视的点-10出现了两次。这不是样例出错而是两种不同的括号分组方式恰好算出了同一个数值。题目要的是“每一种分组方式对应的结果”而不是“去重后的结果集合”。这一点会直接影响后面的数据结构选择。1.2 抓住本质括号改变的是“最后执行哪个二元运算”普通四则运算默认有优先级先乘除后加减但括号的加入让任何一个运算符都可能先执行也可能最后执行。换句话说数字是叶子节点运算符是内部节点每种加括号方式对应一棵二叉树最终结果就是这棵树的后序遍历计算结果。举一个最简单的例子23*4没括号时按优先级先算乘法得到 14如果加括号变成(23)*4那最后执行的运算从乘法变成了加法结果变成 20。所以这道题表面上在问“有几种加括号方式”本质上是在问“能构造出多少棵不同的运算二叉树”。想明白这一点后面的递归思路就顺理成章了。2. 为什么从“穷举括号”入手会绕远路2.1 括号方案数量增长极快卡特兰数如果表达式里有n个运算符那么合法的括号化方案数并不是普通排列数而是卡特兰数[ Catalan(n) \frac{1}{n1}\binom{2n}{n} ]用几个具体的数感受一下运算符个数 n括号方案数011122354145421016796159694845如果先写一个回溯函数生成所有合法括号串再把括号串映射到原表达式上光生成括号串这一步就已经是指数级了。更麻烦的是把括号串和表达式片段正确对齐还很容易出错比如括号不能插在数字中间、某些括号组合会改变数字顺序等等。我自己一开始就是这么想的写完发现又慢又容易崩果断放弃。2.2 穷举括号还会带来大量重复子问题用111来举例。它在最外层有两种切法把第一个当成最后一步右侧子问题是11把第二个当成最后一步左侧子问题也是11同一个11在顶层就被计算了两遍。在更长的表达式里这种重复子问题会大量出现。如果你只是机械地枚举括号而不去缓存子表达式结果运行成本会比理论上的卡特兰数还要高出一截。所以正确思路不是去“摆放括号”而是递归地决定“最后一次运算发生在哪个运算符上”。判断一个运算符是不是最后一步等价于判断以它为根节点的二叉树结构。这个视角的转变是整个解法的关键。3. 分治递归实现每次只在运算符上切一刀3.1 递归公式和终止条件记f(s)表示字符串s所有可能的计算结果集合。对于s中的每一个运算符op它把字符串分成左右两部分左半部分f(left)右半部分f(right)左右两边各自的所有结果都要用当前运算符两两组合一次。所以递归公式可以写成f(s) 对所有满足 s[i] 是运算符的 i 遍历 f(s[:i]) 中的 a 遍历 f(s[i1:]) 中的 b 把 a op b 加入结果终止条件很简单如果s里没有运算符说明这段就是纯数字直接返回[int(s)]。为什么这样能覆盖所有括号方案因为任意一个完整加括号表达式的最后一步运算一定对应表达式里某一个运算符。以它为界整体被切成左右两个独立子表达式而这两个子表达式又可以继续递归切分。递归穷举所有“最后一步”的选择恰好就对应了所有可能的括号结构。整个过程完全没有显式生成括号括号只是递归树的自然投影。3.2 完整可运行代码下面是带记忆化的完整实现内部递归函数返回tuple避免使用可变列表做缓存值from functools import lru_cache from typing import List, Tuple import operator OPS { : operator.add, -: operator.sub, *: operator.mul, } class Solution: def diffWaysToCompute(self, expression: str) - List[int]: lru_cache(None) def dfs(s: str) - Tuple[int, ...]: res [] for i, ch in enumerate(s): if ch in OPS: left_results dfs(s[:i]) right_results dfs(s[i 1:]) for a in left_results: for b in right_results: res.append(OPS[ch](a, b)) if not res: res.append(int(s)) return tuple(res) return list(dfs(expression))这里有几个细节值得说明if not res是终止条件。扫描完整段字符串都没发现运算符说明s是纯数字res还是空列表此时把int(s)加进去返回单元素元组。使用operator.add、operator.sub、operator.mul之后、-、*三种分支统一成一行代码干净很多。内部返回tuple主要是防止调用方不小心修改到缓存列表缓存的 key 是svalue 应该是不可变对象更稳妥。3.3 手推2-1-1的递归过程用代码的扫描顺序大致走一遍扫描到下标 1 的-左边dfs(2)返回(2,)右边dfs(1-1)返回(0,)组合得到2 - 0 2。这对应(2-(1-1))。扫描到下标 3 的-左边dfs(2-1)返回(1,)右边dfs(1)返回(1,)组合得到1 - 1 0。这对应((2-1)-1)。所以代码返回[2, 0]。题目允许任意顺序判题时会忽略顺序。自己写本地测试时最好把结果排序后再比较避免被顺序影响。2*3-4*5的过程也一样只是每个层级都有更多切分点递归树会更大。只要有耐心把其中一棵子树完整画出来就能感受到分治递归和二叉树结构的一一对应关系。4. 记忆化优化和复杂度真相不要背“记忆化多项式”4.1 同一个子串会被多个父请求反复计算以2*3-4*5为例顶层按中间的-切分时右侧子问题是4*5而按第一个*切分后右侧子问题是3-4*5继续往下切还有4*5。也就是说4*5会出现在不同的递归分支里。没有缓存时这些相同子串每次都要重新完整算一遍。加上lru_cache(None)之后每个不同的字符串参数只会计算一次。同一个表达式内部有多少个不同子串上限大概是O(n^2)级别这里的n指的是运算符个数。4.2 复杂度要分两层说很多博客会说“用记忆化后复杂度变成多项式”这其实只说对了一半。记忆化确实消除了重复计算同一个子表达式的开销但每个子表达式的结果集本身可能非常庞大。一个内部包含k个运算符的子表达式它的结果数量最多可以达到Catalan(k)。合并左右结果时需要把两边结果两两相乘这个笛卡尔积成本必须真实付出因为题目要求枚举所有结果。也就是说记忆化以前同一个子问题会在不同父分支中被重复递归额外成本是指数级的放大。记忆化以后每个不同子表达式只算一遍但最终输出结果集本身仍然可能是指数规模的。所以在最坏情况下这道题的时间复杂度仍然是超多项式的。如果面试时被问到复杂度不能只丢一句“记忆化后是 O(n²)”。更准确的说法是记忆化减少了重复递归的常数级甚至更大的冗余但由于输出规模本身可能是卡特兰数量级整体复杂度不能避免指数增长。判断一个问题能不能这样优化关键看你要的到底是“全部结果”还是“最优值/计数值”。这道题要全部结果输出规模天然就大。后面第 6 节会专门对比这种差异。4.3 实际题目的数据范围决定了这个解法很稳虽然最坏情况理论上是指数级但这类题目的输入长度通常不会太大运算符个数一般控制在 10 到 15 以内。Catalan(15)约 969 万对于工程代码来说虽然不算轻但 Python 在合理时限内勉强能跑运算符数量到 17、18 以上就非常吃力了。所以实际刷题时遇到这类“枚举所有结果”的问题第一优先考虑分治递归加记忆化基本不会错。真正要担心的是输出规模本身是否超过题目限制而不是递归深度。递归深度只和运算符个数同级完全不用怕爆栈。5. 踩坑记录几处“看起来没毛病但拿去一提交就错”的细节5.1 多位数不要在切片之前逐字符转数字这道题的输入可能包含多位数比如1122。用上面代码的写法切到运算符时左边int(11)是 11右边int(22)是 22完全没问题。但如果你先做了这种预处理nums list(expression) # 比如把 1 和 1 当成两个独立的 1那就完蛋了。多位数被拆成单个数字所有计算结果都会错。正确做法就是依赖int(s)对整段子串做解析或者提前写一个 tokenizer把连续数字合成一个整体。千万不要用int(s[i])去转单个字符后再拼。5.2 重复结果不能用集合去重看题解时偶尔能看到有人把结果用set去重理由是“结果重复了没什么意义”。这道题恰恰相反每一种不同的括号分组都算独立结果哪怕数值相同也要保留。2*3-4*5里面的-10出现两次如果去重输出就只剩四个数判题直接判错。所以内部res一定要用列表不要为了“看起来更优”换成set。5.3 递归终止条件别写成if not int(s)单表达式0是一个很容易踩的边界。有人会在递归基态这样写if not int(s): res.append(0)这看起来是想判断“s 是不是数字 0”但int(0)等于 0布尔值为False结果什么都不会加返回空列表整个递归就断了。正确写法是通过res是否为空来判断if not res: res.append(int(s))只有扫描完整段都没找到运算符时才把int(s)作为唯一结果加入。这个if not res是“是否发现运算符”的标记不是“s 这个数字是否为 0”的判断。5.4 本地测试记得对结果排序由于代码的扫描顺序是从左到右返回的结果顺序可能和官方样例的展示顺序不同。判题系统一般做顺序无关的比较但你自己在本地写断言时要小心被顺序误导。建议这样写测试assert sorted(sol.diffWaysToCompute(2*3-4*5)) [-34, -14, -10, -10, 10] assert sorted(sol.diffWaysToCompute(2-1-1)) [0, 2]排序后既保留重复值又不受返回顺序影响。这是我刷这道题时吃过两次亏之后才养成的习惯。5.5 输入是否有空格和负数题目版本不同输入形式可能会有差别。常见版本是只有数字和 - *没有空格也没有一元负号。但如果你的子问题解析遇到-5这种输入上面的分治逻辑会出问题因为扫描-时左边是空串。比较稳妥的做法是写一个 tokenizer 先把数字和运算符拆开然后基于 token 数组做区间递归。如果确定题目保证输入合法且没有一元负号直接字符串切片方案最简洁但我个人建议先读清楚题目的约束。6. 从这道题抽象出“分治记忆化”套路识别信号与应用扩展6.1 同样思路能直接套的题目类型这道题属于“区间分割组合子结果”的经典模板很多题目只是换了壳子。题目特征子问题是什么合并方式复杂度特点表达式加括号求所有值一段表达式的结果集合左右结果两两做运算枚举输出结果集本身可能指数级布尔表达式加括号计数一段表达式为 True/False 的方案数左右计数按运算符转移只统计数量可做到 O(n³) 级别生成所有二叉搜索树区间内所有合法根节点/树左右子树列表两两拼接必须构造函数列表规模指数级矩阵链乘最小代价区间最小乘法次数遍历切分点取最小只求最优值状态是标量O(n³)布尔表达式计数那道题和本题几乎一模一样只是返回的不再是“所有结果”而是“结果为 True 的方案数”。由于只需要计数状态可以收敛成(trueCount, falseCount)两个数字组合时用乘法和加法完成转移所以复杂度可以从指数级降到多项式。反过来看本题之所以无法多项式化是因为必须输出所有具体结果。6.2 我判断一个题适不适合这个套路的三个信号第一题目里出现“所有可能的结果”“所有方式”“所有树”这类字眼说明要枚举而不是只求一个最优值。第二能找到一个天然的“切割点”。对于表达式问题是最后执行的运算符对于二叉搜索树问题是根节点对于矩阵链乘问题是最后一次相乘的分界点。找到切割点后左右两边互相独立。第三父问题的答案能通过左右子问题的答案组合得到而且组合方式在数学上是封闭的。比如这里左右结果做一次加减乘组合后还是合法结果。如果以上三个信号都满足优先往分治递归方向想再根据是否需要记忆化去优化。6.3 我的复盘顺序和自问清单每次碰到这类题我习惯按固定顺序走一遍先手算最小样例把递归树画出来确认每个运算符确实都能作为“最后一步”。写最朴素的递归版本不用缓存先保证小样例正确。测通之后再加lru_cache对比前后运行时间验证哪些子问题被重复计算了。回答复杂度时先把不同子串的数量上限讲出来再把结果集规模单独拎出来说避免被面试官追问。最后检查几个隐藏边界结果要不要去重、输入有没有可能只有一个数字、有没有空格、有没有一元负号。我自己的切身感受是这道题只看题解永远觉得很简单但真正自己画一遍递归树再亲手踩一次重复结果没保留、0被漏掉的坑才会真正理解分治递归和表达式二叉树之间的关系。建议你拿到代码后把2*3-4*5的递归树完整展开一次效果比连刷十道同类题都要好。