96. Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?

Example:

Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

预备知识

卡特兰数，又称卡塔兰数，卡特兰数是「组合数学」中一个常出现在各种计数问题中的数列。其递推式为：

卡特兰数的应用：

1. 给定 n 个节点组成不同的二叉树个数
   Cn 表示有 n 个节点组成不同构二叉树的方案数。下图中，n 等于3，圆形表示节点，月牙形表示什么都没有。

在本题中，n 为 BST 节点个数，则
当 n = 0 时，其 Unique Binary Search Trees 有 1 种，因为空树也算是一种二叉树。

当 n = 1 时，可以看作是其左子树个数乘以右子树个数，此时左右子树都是空树，即均为 1 种，则其 Unique Binary Search Trees 有 种。

当 n = 2 时，由于 1 和 2 都可以为根，所以当 1 为根时，有 种；同理当 2 为根时，有 种；因此总共有 种, 形式化的公式为：

dp[0]*dp[1] 表示1 为 根，根据 BST 的性质，此时左子树为空树；dp[1][0]表示 2 为根，根据 BST 的性质，此时右子树为空树)

当 n = 3时，递推可以得到为 5 种,即

根据以上的关系，利用 DP 方法可解：

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n+1, 0);
        dp[0] = 1;
        dp[1] = 1;
        
        for(int i = 2; i <= n; i++){
            for(int j = 0; j < i; j++){
                dp[i] += dp[j] * dp[i-j-1];
            }
        }
        return dp[n];
    }
};