LC.P823[带因子的二叉树]

方法一：记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    
    private static final int MOD = (int) 1e9 + 7;
    long[] cache;
    Map<Integer, Integer> map;
    int[] arr;

    public int numFactoredBinaryTrees(int[] arr) {
        this.arr = arr;
        int n = arr.length;
        Arrays.sort(arr);
        map = new HashMap<>(n);
        for (int i = 0; i < n; ++i) map.put(arr[i], i);
        cache = new long[n];
        Arrays.fill(cache, -1);
        long ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += dfs(i);
        }
        return (int) (ans % MOD);
    }

    private long dfs(int i) {
        if (cache[i] != -1) return cache[i];
        int x = arr[i];
        long ans = 1;
        for (int j = 0; j < i; ++j) { // x 的因子一定比 x 小
            int y = arr[j];
            if (x % y == 0 && map.containsKey(x / y)) {
                ans += dfs(j) * dfs(map.get(x / y));
            }
        }
        return cache[i] = ans;
    }
}
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(n)$

方法二：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {

    private static final int MOD = (int) 1e9 + 7;

    public int numFactoredBinaryTrees(int[] arr) {
        Arrays.sort(arr);
        int n = arr.length;
        Map<Integer, Integer> map = new HashMap<>(n);
        for (int i = 0; i < n; ++i) map.put(arr[i], i);
        long ans = 0;
        long[] f = new long[n];
        for (int i = 0; i < n; ++i) {
            f[i] = 1;
            int x = arr[i];
            for (int j = 0; j < i; ++j) {
                int y = arr[j];
                if (x % y == 0 && map.containsKey(x / y)) {
                    f[i] += f[j] * f[map.get(x / y)];
                }
            }
            ans += f[i];
        }
        return (int) (ans % MOD);
    }
}
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(n)$