LeetCode:96

Posted on 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int numTrees(int n) {
        if(n==0) {return 0;}
        int[] res = new int[n+1];
        res[0] = 1;
        res[1] = 1;
        for(int i = 2; i < n+1; i++) {
            for(int j = 1; j<= i; j++) {
                res[i] += res[i-j] * res[j-1];
            }
        }
        return res[n];
    }
}
  1. 确定一个根节点
  2. 小于根节点的值组成左子树，大于根节点的值组成右子树
  3. 左子树的组合总数乘以右子树的组合总数，即为当前根节点可能形成的树的总数。

举例：
当n=6，选取根节点为i=3的时候，此时树的可能性为[1,2]组成子树的可能[4,5,6]组成子树的可能,实际上[4,5,6]组成子树的总数就等于[1,2,3]组成子树的总数。
因此可以得出dp公式 F(i, n) = G(i-1) G(n-i)，其中G(i-1)就是左子树，G(n-i)就是右子树。

参考：https://leetcode.com/problems/unique-binary-search-trees/discuss/31666/DP-Solution-in-6-lines-with-explanation.-F(i-n)-G(i-1)-*-G(n-i) 下用户@lizhu5058的解释。