LC96 Unique Binary Search Trees

本题链接：Unique Binary Search Trees

本题标签：Tree, Dynamic Programming

本题难度：

英文题目 中文题目

---

方案1：

class Solution {
public:
    int numTrees(int n) {
        int *G = new int[n + 1]{0};
        G[0] = G[1] = 1;
        
        for(int i = 2; i <= n; ++i)
            for(int j = 1; j <= i; ++j)
                G[i] += G[j - 1] * G[i - j];  
        return G[n];
    }
};
// G[0] = G[1] = 1
// G[n] = F[1,n] + F[2,n] + ... + F[n,n]
// F[i,n] = G[i-1] * G[n-i]
// G[n] = G[0] * G[n-1] + G[1] * G[n-2] + ... + G[n-1] * G[0]
// 卡特兰数。以1到n中的每一个数作为根节点，划分为左右BST子树，然后在左右BST子树中重复划分。这个过程的数学原理就是卡特兰数乘积和。

时间复杂度：

空间复杂度：

---