题目描述
思路解析
一句话答案：LeetCode 823 带因子的二叉树：排序后 dp[v] 记以 v 为根的树数，枚举每对因子 a×b=v 累加 dp[a]×dp[b]，答案是所有 dp 之和取模。命门在乘法组合，时间 O(n²)、空间 O(n)。
非叶结点等于两孩子相乘，这树怎么数
给一个数组 arr，元素互不相同、都大于 1。拿这些数当结点搭二叉树，同一个数可反复用，规矩是每个非叶结点必须正好等于左孩子乘右孩子。问能搭出多少种不同的树，对 1e9+7（一个常用大质数）取余。
拿题面的 arr = [2, 4, 5, 10]，答案是 7：四个数各自单独成一棵只有根的树是 4 棵，再加 4 = 2×2、10 = 2×5、10 = 5×2 三棵有孩子的凑够 7（左 2 右 5 与左 5 右 2 算两棵）。
为什么不能把所有树形硬枚举一遍
一个数当根、两个孩子又各能往下长子树，形状随规模成倍翻，把每种树都摆出来一棵棵数根本数不完；而且同一棵子树在很多处被从头重算。既然「以某数为根能搭几棵树」能独立回答又反复用到，算一次存下来就行，就是动态规划那套。
为什么先排序，dp[v] 定成什么
先把 arr 从小到大排序。定义 dp[v] 为「以 v 为根能搭多少棵合法树」。v 当非叶根就得拆成两因子 a×b = v 当左右孩子，而 a、b 都大于 1，都严格小于 v。
a、b 都比 v 小，排完一定排在 v 左边，算 dp[v] 时它们的 dp 早已就绪；不排序会取到没累加完的半成品。
dp[a]×dp[b] 为什么是相乘不是相加
dp[v] 从 1 起步——单个数本身就是一棵只有根的合法树。再枚举每对满足 a×b = v 且 a、b 都在 arr 里的因子，把 dp[a]×dp[b] 累加进去。这里用乘法原理（两件事各自独立选，总方案是各自方案数相乘）：左孩子有 dp[a] 种长法、右孩子有 dp[b] 种，各挑各的互不牵制，组合就是 dp[a]×dp[b] 种。
枚举只需扫一个因子 a，商 c = v÷a 若在 arr 里就配一对。累加是相乘不是相加，最易写反。
拿 [2,4,5,10] 把四个 dp 逐格填出来
排序后是 2, 4, 5, 10，dp 全从 1 起步。dp[2]：前面无更小的数，保持 1。dp[4]：先记单点 1 棵，试 2，4÷2 = 2 在表里，累加 dp[2]×dp[2] = 1，得 2。
dp[5]：试 2、试 4 都除不尽，锁定 1。dp[10]：先记单点 1 棵；试 2，10÷2 = 5 在表里，累加 dp[2]×dp[5] = 1，变 2；试 5，10÷5 = 2 在表里，累加 dp[5]×dp[2] = 1，变 3。四格是 1、2、1、3，答案 1+2+1+3 = 7，与题面对上。
dp[a]×dp[b] 不取余为什么会溢出成负数
外层枚举根、内层枚举较小因子，两层都是 n；配「值到下标」哈希表（一种能瞬间查『某个数在不在』的表）让「商在不在数组」做到 O(1)，整体 O(n²)，空间 O(n)。arr 全是质数或两两互质（任意两个数没有大于 1 的公因子）时，谁都拆不出表里的因子，答案就等于元素个数。
累加时 dp[a]×dp[b] 会撑爆整型，每加不立刻对 1e9+7 取余就溢出翻成负数、答案全错；a≠c 那对左右不对称，「左 a 右 c」和「左 c 右 a」是两棵不同的树，内层扫到 a 和扫到 c 各计一次，少数一遍就漏掉一半组合。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这句口诀：排序、dp 从 1 起步、枚举因子对、乘法原理累加、最后求和。后面每一帧都在套它。
第一步先排序：2, 4, 5, 10。排序是为了保证算到 x 时，比它小的因子都已经算好 dp 了。右边面板就是 dp 表，现在每个值都是 1。
dp[x] 为什么从 1 起步？因为任何一个数单独拎出来就是一棵只有根的合法树。这 4 个 1，就是示例 7 棵里最朴素的 4 棵。
强调一下顺序：因子 b、c 都严格小于它们的乘积 x，排序后它们一定排在 x 前面、dp 已经算好。所以从左往右一个个算，永远能拿到现成的因子 dp。
先看最小的 2。它要拆成两个因子相乘，最小也得是别的数当孩子，但没有比它更小的数在表里，所以 2 只能是单结点，dp[2] 保持 1。
轮到 4。先把它自己当单结点那 1 棵记上，dp[4] 从 1 起步。接着去前面找：有没有两个数相乘正好等于 4，能当它的左右孩子。
试因子 2：4 能被 2 整除，商是 2，而 2 也在表里。这就凑成一对合法孩子，左孩子 2、右孩子 2 相乘正好 4。
用乘法原理：左子树有 dp[2] = 1 种长法，右子树有 dp[2] = 1 种，自由组合就是 1 × 1 = 1 种，累加进 dp[4]，现在是 2。
4 的因子对枚举完了，dp[4] 最终是 2：单结点 1 棵，加上各因子对带来的组合。
轮到 5。先把它自己当单结点那 1 棵记上，dp[5] 从 1 起步。接着去前面找：有没有两个数相乘正好等于 5，能当它的左右孩子。
试因子 2：5 除以 2 除不尽，2 根本不是 5 的因子，当不了它的孩子，跳过。
试因子 4：5 除以 4 除不尽，4 根本不是 5 的因子，当不了它的孩子，跳过。
5 前面的数都没法两两相乘等于它，所以它只有单结点这一种，dp[5] 锁定为 1。
轮到 10。先把它自己当单结点那 1 棵记上，dp[10] 从 1 起步。接着去前面找：有没有两个数相乘正好等于 10，能当它的左右孩子。
试因子 2：10 能被 2 整除，商是 5，而 5 也在表里。这就凑成一对合法孩子，左孩子 2、右孩子 5 相乘正好 10。
用乘法原理：左子树有 dp[2] = 1 种长法，右子树有 dp[5] = 1 种，自由组合就是 1 × 1 = 1 种，累加进 dp[10]，现在是 2。
试因子 4：10 除以 4 除不尽，4 根本不是 10 的因子，当不了它的孩子，跳过。
试因子 5：10 能被 5 整除，商是 2，而 2 也在表里。这就凑成一对合法孩子，左孩子 5、右孩子 2 相乘正好 10。
用乘法原理：左子树有 dp[5] = 1 种长法，右子树有 dp[2] = 1 种，自由组合就是 1 × 1 = 1 种，累加进 dp[10]，现在是 3。
10 的因子对枚举完了，dp[10] 最终是 3：单结点 1 棵，加上各因子对带来的组合。
四个 dp 都算好了：2 是 1 棵，4 是 2 棵，5 是 1 棵，10 是 3 棵。每个数当根能搭多少树，面板里一目了然。
每个数都可以当整棵树的根，所以答案是把所有 dp 加起来：1 + 2 + 1 + 3 = 7。
于是 arr = [2, 4, 5, 10] 一共能搭出 7 棵合法二叉树，和示例对上了。数据大时记得每步对 1e9+7 取余。
边界先想清：单个数、两个互质数、全质数，这些都搭不出非叶结点，答案就是元素个数。
面试重点：讲清「枚举因子天然覆盖左右对称」和「哈希表加速判断因子是否存在」两点。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def numFactoredBinaryTrees(self, arr: List[int]) -> int: mod = 10**9 + 7 n = len(arr) arr.sort() idx = {v: i for i, v in enumerate(arr)} f = [1] * n for i, a in enumerate(arr): for j in range(i): b = arr[j] if a % b == 0 and (c := (a // b)) in idx: f[i] = (f[i] + f[j] * f[idx[c]]) % mod return sum(f) % mod复杂度
- 时间：O(n²)，双层枚举根与因子，哈希查商 O(1)
- 空间：O(n)，dp 数组 + 值到下标的哈希表
易错点
面试追问把动画讲成自己的话
追问为什么枚举一个因子 b 就够，不会漏掉 (c, b) 这种对称情况？
追问这题和普通的线性 dp 有什么不同？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最长的斐波那契子序列的长度
LeetCode 873 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题