※ 引述《ZooseWu (动物园 公告)》之铭言：
: 思路：
: 动态规划基本题
: 判断两个节点有没有都在arr里面
: 有的话就把两个child的可能性乘起来
: 另外宣告一个Set
: 可以让判断乘数有没有在阵列中的时候不用再找整个阵列一次
: 因为Set的时间复杂度是O(1)
: 原本想说可以不用理会乘数跟被乘数交换的状况
: 反正最终都会轮到
: 但是后来看了别人的解答后
: 发现我没有考虑到数字很大的情况下
: n跟sqrt(n)会差很大
: 有加上这个判断可以让时间复杂度从O(n^2)降到O(n*sqrt(n))
这里感觉有点怪
sqrt 和 n 应该没关系 你要比的应该是 sqrt(max(arr))
举个例子 [1,2,3,4,5,13,169], n = 7
更新 dp[169] 的时候还是要扫完整个 arr
时间上是有变好 但复杂度没有变 或者是要加类似 min(n, sqrt(max(arr)))
之类的东西进去