※ 引述《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)))
之類的東西進去