96. Unique Binary Search Trees

这道题使用动态规划解决

对于1...n的节点，我们从中挑出一个节点 i (1 <= i <=n)作为根节点。在这种情况下，所有的情况的总数是1...i-1和i+1...n的乘积，G(n) = G(i -1) * G(n - i)

在给定n的情况下，结果是遍历i从1到n的结果的总和。G(n) = G(0)G(n-1) + ...+G(i -1) * G(n - i) + ... G(n-1)G(0)

这个我们用脑子想想就知道
G(0) = 1;
G(1) = 1;

我们从n=2开始，一步步往后算。代码如下。

class Solution {
    public int numTrees(int n) {
        
        int[] data = new int[n + 1];
        data[0] = 1;
        data[1] = 1;
        
        for(int i = 2; i <= n; i++){
            int current = 0;
            for(int j = 1; j <= i; j++){
                current += data[j - 1] * data[i - j];
            }
            data[i] = current;
        }
        
        return data[n];
    }
}