96.md

#96. Unique Binary Search Trees 题目链接

public class Solution {
    public int numTrees(int n) {
        // 创建一个数组来记录
        int[] g = new int[n + 1];
        // 前两个设为1，应为1个结点和0个结点都只有一种情况
        g[0] = g[1] = 1;
        /*
            自底向上的动态规划
            假设f(1,5)是当n等于5的时候，以结点1为顶点的所有可能情况
            g[n] = f(1,5)+f(2,5),...+f(5,5)
            f(2,5)的左子树所有可能情况为g(1),右子树可能情况为g(3)
            所以f(2,5)=g(1)*g(3)，其他同理，这样就可算出递推公式
         */
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                g[i] += g[j] * g[i - 1 - j];
            }
        }
        return g[n];
    }
}