【每日一题Day309】LC823带因子的二叉树 | dp

class Solution {
    public static final int MOD = (int)(1e9 + 7);
    public int numFactoredBinaryTrees(int[] arr) {
        Arrays.sort(arr);
        long res = 0L;
        int n = arr.length;
        long[] dp = new long[n];
        Map<Integer,Integer> index = new HashMap<>();
        for (int i = 0; i < n; i++){
            index.put(arr[i], i);
        }
        Arrays.fill(dp, 1L);
        for (int i = 0; i < n; i++){
            for (int j = 0; j < i; j++){
                if (arr[i] % arr[j] == 0 && index.containsKey(arr[i] / arr[j])){
                    dp[i] += dp[j] * dp[index.get(arr[i] / arr[j])] ;
                }
            }
            res += dp[i];
        }
        return (int)(res % MOD) ;
    }
}