主題
題目連結：
題目意譯：
給定一個相異整數陣列 arr，其中每個整數 arr[i] 嚴格大於 1。
我們將使用這些整數來製造一個二元樹，而每個數字可以被使用任意次。每個非葉節點之數值應等於其小孩節點的數值之乘積。
回傳我們能製造出的二元樹之數量。答案可能會太大，因此將其模 10 ^ 9 + 7 後再回傳。
限制：
1 ≦ arr.length ≦ 1000
2 ≦ arr[i] ≦ 10 ^ 9
arr 中的整數彼此相異。
範例測資：
範例 1：
輸入： arr = [2,4]
輸出： 3
解釋： 我們可以製造出這些樹：[2] 、 [4] 、 [4, 2, 2]
範例 2：
輸入： arr = [2,4,5,10]
輸出： 7
解釋： 我們可以製造出這些樹：[2] 、 [4] 、 [5] 、 [10] 、 [4, 2, 2] 、 [10, 2, 5] 、 [10, 5, 2]。
解題思維：
假設現在我們已經知道各自以 2 ～ x - 1（x ≧ 2）作為根節點的數值可以產生多少樹（先忽視 arr 中的數字，先討論最一般的情形。注意，這邊依舊不會出現數字 1）。
而現在我們想要知道以 x 作為根節點數值有多少二元樹，則我們需要掃過 x 所有的因數。而我們只需要檢查 2 ～ sqrt(x)（即 x 的平方根）之間的數字是否為其因數。
如果某一數 i 是 x 的因數，則 x ÷ i 也將是 x 的因數。所以我們可以將左子樹的根節點數值設為 i，右子樹的則設為 x ÷ i（因此接下來就需要 i 和 x ÷ i 各自可以產生的二元樹之數量相乘）。又或是反過來；除非 i 與 x ÷ i 是同一種數字，則這個情況下交換沒有意義。
有了上述的核心想法後，就可以回到 arr 本身了。從上面可以看到，我們把 arr 中的數字由小排到大會比較好處理。
然後我們把上面的想法敘述重寫一下：
假設現在我們已經知道各自以 arr[0] ～ arr[i - 1]（i ≧ 1）作為根節點的數值可以產生多少樹。
而現在我們想要知道以 arr[i] 作為根節點數值有多少二元樹，則我們需要掃過 arr[i] 所有的因數。而我們只需要檢查所有 arr[j]（其滿足位於 2 ～ sqrt(arr[i]) 之間）是否為其因數。
如果某一數 arr[j] 是 arr[i] 的因數，則 arr[i] ÷ arr[j] 也將是 arr[i] 的因數。但這不代表 arr[i] ÷ arr[j] 存在於 arr 之中，所以要先檢查。
如果真的存在，則我們可以把左子樹的根節點數值設為 arr[j]，右子樹的則設為 arr[i] ÷ arr[j]（因此接下來就需要 arr[j] 和 arr[i] ÷ arr[j] 各自可以產生的二元樹之數量相乘）。又或是反過來；除非 arr[j] 與 arr[i] ÷ arr[j] 是同一種數字，則這個情況下交換沒有意義。
一般這個情況下我們通常會使用一個陣列來儲存每一種數字的答案，只是現在 arr[i] 的數字可以大到 10 ^ 9。而我們不可能去開這麼大的陣列，且重點是——大部分位置存的值都是 0（因為不存在於 arr 中）。
因此我們可以使用雜湊表（Hash Table）來存每一種數字 arr[i] 的答案。接著就按照一般動態規劃（Dynamic Programming，DP）的題目去求解即可。
題外話：其實還是可以使用陣列來存的。不過這個就交給讀者們去想。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
