LeetCode带因子的二叉树（动态规划）

给出一个含有不重复整数元素的数组，每个整数均大于 1。

我们用这些整数来构建二叉树，每个整数可以使用任意次数。

其中：每个非叶结点的值应等于它的两个子结点的值的乘积。

满足条件的二叉树一共有多少个？返回的结果应模除 10 ** 9 + 7。

示例 1:

输入: A = [2, 4] 输出: 3 解释: 我们可以得到这些二叉树: [2], [4], [4, 2, 2]

示例 2:

输入: A = [2, 4, 5, 10] 输出: 7 解释: 我们可以得到这些二叉树: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].

提示:

1 <= A.length <= 1000. 2 <= A[i] <= 10 ^ 9.

$思路分析：$首先我们知道只有较小的元素才能作为叶节点（或者子树），并且如果我们需要计算某个较大的元素为根节点的所有情况，则我们需要先计算比他小的且能放在左右子树下的节点为根的二叉树个数。比如输入[10，2，5]，我们并不能直接计算以10为根的二叉树个数，我们需要先计算能放在它左右子树位置的节点为根的二叉树个数，以2为根的二叉树个数 = 1，以5为根的二叉树个数为1，所以以10为根的二叉树个数为1 + 2，其中前面的1为自身[10]，后面的2为[10，2，5]，[10，5，2]，起始就是dp[10] = dp[2] * dp[5] + dp[5] * dp[2] + dp[10]（dp[10]初始化为1）.这说明我们需要将A进行升序排序，按照升序的顺序遍历以A[i]为根节点的二叉树个数。

dp[A[i]]储存以A[i]为根节点的二叉树个数 状态转移方程： dp[A[i]] = (dp[A[i]] + (dp[A[j]] * dp[A[i] / A[j]] % M)) % M;//A[i]为根节点，A[j]为左子树，A[i] / A[j]为右子树

class Solution { public: int numFactoredBinaryTrees(vector<int>& A) { if(A.size()==0){ return 0; } map<int, long> dp;//dp[A[i]]储存以A[i]为根节点的二叉树个数 sort(A.begin(), A.end());//升序排序 int M = 1000000007, Asize = A.size(); //升序遍历A，计算以A[i]为根的二叉树个数 for (int i = 0; i < Asize; ++i){ dp[A[i]] = 1;//初始化为1（二叉树只有自身一个节点） for (int j = 0; j < i; ++j){ //这层循环用于确定左子树节点A[j],以及右子树节点A[i] / A[j](如果A[i] / A[j]存在，必定也会访问到A[i] / A[j]左子树、A[j]右子树这种情况) if (A[i] % A[j] == 0){ dp[A[i]] = (dp[A[i]] + (dp[A[j]] * dp[A[i] / A[j]] % M)) % M; } } } long res = 0;//最后将所有元素A[i]为根的二叉树进行求和 for (const auto &item : dp){ res = (res + item.second) % M; } return res; } };