作者:
Rushia (みけねこ的鼻屎)
2023-10-26 22:12:13https://leetcode.com/problems/binary-trees-with-factors/description/
823. Binary Trees With Factors
給你一個陣列 arr,裡面的數字不重複且大於 1,我們可以不限制次數的使用這些
數字構建出一個二元樹,這個二元樹需要滿足左右節點的值相乘等於父節點,求出
共有幾種組合。
Example 1:
Input: arr = [2,4]
Output: 3
Explanation: We can make these trees: [2], [4], [4, 2, 2]
思路:
1.動態規劃,如果 arr[i] = arr[j] * arr[k] 則他可以組成一個三個節點的二元樹
假設 dp(n) 表示這個數字共有幾種組合,每個數字都當根節點的話至少有一種組合,
所以我們把每個數字的組合初始化為 1。
2.我們可以先把 arr 從小到大排序,這樣只需要檢查比 i 小的 arr[j] 是否存在因數
arr[k](檢查所有索引小於 i 的 arr),如果存在的話可以構建出
dp(arr[j]) * dp(arr[k]) 種樹,把他累加到 dp(arr[i]),因為我們排序過的關係,
所以處理到 i 的時候,dp(arr[j]) 和 dp(arr[k]) 一定已經計算完。
3.最後把 dp(arr[0], ....arr[n - 1]) 加總就是答案,因為數字很大所以要模 1e9+7。
Java Code: