LC.P96[不同的二叉搜索树]

方法一：区间DP

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int numTrees(int n) {
        int[] f = new int[n + 1];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                f[i] += f[j - 1] * f[i - j];
            }
        }
        return f[n];
    }
}
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(n)$

方法二：数学—卡特兰数

卡特兰数，公式为 $C_{n + 1} = \frac {C_{n} \times (4n + 2)} {n + 2} $

1
2
3
4
5
6
7
class Solution {
    public int numTrees(int n) {
        long ans = 1;
        for (int i = 0; i < n; i++) ans = ans * (4 * i + 2) / (i + 2);
        return (int)ans;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$