题目

用有向无环图描述表达式 ，需要的顶点个数至少是( )。

错因

B

意识到要合并相同的变量（x、y 各只占 1 个叶子），但漏掉了"公共子表达式 x+y 也可以共享" 这一步。两次 (x+y) 各算了一个加号节点：x(1) + y(1) + +(2) + /(1) + *(1) = 6。

C

只合并了部分变量。例如把所有 y 合并为 1 个叶子，但把 x 当成 3 次独立出现（在 (x+y) 内 2 次、在分母 1 次），也没合并 (x+y)：x(3) + y(1) + +(2) + /(1) + *(1) = 8。本质是对"DAG 中相同节点共享"的力度认识不到位。

D

完全把 (x+y)*((x+y)/x) 当成普通表达式树画，每个变量出现一次就建一个叶子节点，加号也各自独立：x(3) + y(2) + +(2) + /(1) + *(1) = 9。没用上 DAG 共享子表达式的优势，相当于退化成了二叉表达式树。

总解析

核心思路：DAG 表示表达式时，完全相同的子表达式必须共用同一个节点，这是与表达式树的关键区别，也是 DAG 节点数远少于表达式树的原因。

逐层识别相同部分：

1. 变量 x 和 y（叶子）：DAG 中同名变量共用一个叶子节点。所以无论 x 出现 3 次、y 出现 2 次，都各自只占 1 个叶子。

2. 公共子表达式 x+y：在原表达式里出现了两次（外层 (x+y)* 与内层 (x+y)/x）。它们的两个操作数完全相同——同一个 x 节点和同一个 y 节点——所以这两个加法节点也要合并为 1 个 + 节点。

3. 除法 / 和乘法 * 各自只出现一次，无可合并。

清点最终 DAG 顶点：

类型	个数	说明
叶子 x	1	所有 x 共用
叶子 y	1	所有 y 共用
+	1	x+y 共用
/	1	(x+y)/x，左输入指 + 节点、右输入指 x 叶子
*	1	(x+y)*((x+y)/x)，左输入指 + 节点、右输入指 / 节点

共 5 个顶点。

对比表达式树（不合并任何子表达式）：x×3 + y×2 + +×2 + /×1 + *×1 = 9 个，正好对应选项 D。两者差额 4 个节点都是合并公共子表达式带来的节省。

最终答案是 A。