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