题目描述
思路解析动画文字版
记住这套「在运算符处劈开 → 递归两边 → 两两组合」，每个运算符当根就得到一棵表达式树，下面逐棵看。
整个表达式 2-1-1 就是要解的根。它有两个减号，意味着有两个位置可以「最后算」，对应两种加括号方式、两棵表达式树。我们一棵棵展开。
第一种：在第 1 个减号处劈开。左边是数字 2（叶子，直接得 [2]，存进 memo），右边是子表达式 1-1，还要继续往下算（标灰待展开）。
展开右子 1-1：它在自己的减号处再劈成两个叶子 1 和 1。现在这棵树长全了，开始从最底层往上算。
先算右子树：两个叶子都是 1，1 - 1 = 0。子表达式 1-1 算完得 [0]，连同叶子 1 一起存进 memo。
再算根：左边 2 减去 右子树算出的 0，2 - 0 = 2。第一种加括号 (2-(1-1)) = 2，记入结果。
第二种：改在第 2 个减号处劈开。左边是子表达式 2-1（待展开），右边是数字 1。注意右边 dfs("1") 之前算过，直接命中 memo 取 [1]，不重复递归。
展开左子 2-1：劈成叶子 2 和 1。这两个 dfs("2")、dfs("1") 也都在 memo 里，命中缓存直接取值，省掉重复计算。
先算左子树：2 - 1 = 1。子表达式 2-1 得 [1]，存进 memo。
再算根：左子树的 1 减去 右边 1，1 - 1 = 0。第二种 ((2-1)-1) = 0。两种方式都算完，根表达式 2-1-1 的全部结果也存入 memo。
两种加括号分别得到 2 和 0，全部结果 = [0, 2]（每种括号方式各贡献一个值、有重复也全保留，本例正好没有重复）。memo 里五条缓存都还在，子表达式只算了一次。回头看：这个例子里两个减号各当一次根、正好得到两棵树；表达式更长时，每个顶层根还要递归展开左右两边、把两边的多个结果两两组合，所以一个根可能对应多棵树、多个结果。
边界先想清：纯数字直接返回、结果可以重复、顺序不限。
两个高频追问：分治的分裂点是「最后算的运算符」，记忆化砍的是重叠子问题。
参考代码
from typing import Listfrom functools import lru_cacheclass Solution: def diffWaysToCompute(self, expression: str) -> List[int]: @lru_cache(None) def dfs(s: str): ans = [] for i, ch in enumerate(s): if ch in '+-*': for a in dfs(s[:i]): for b in dfs(s[i+1:]): ans.append(a + b if ch == '+' else a - b if ch == '-' else a * b) return tuple(ans or [int(s)]) return list(dfs(expression))复杂度
- 时间：O(Catalan(n))，n 个运算符的不同加括号方式数 = 卡特兰数，结果个数本身就是这个量级
- 空间：O(Catalan(n))，存所有结果 + 递归栈 + memo 缓存
易错点
面试追问把动画讲成自己的话
追问为什么这道题适合分治而不是先算优先级？
追问记忆化在这里到底省了什么？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
至少有 K 个重复字符的最长子串
LeetCode 395 · 中等 · 沿着 分治套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题