96 Unique Binary Search Trees

给定n，判断有多少不同的二叉搜索树。

二叉搜索树，若左子树不空，左子树上的所有节点的值均小于根节点的值，若右子树不空，则右子树上所有节点值均大于根节点值。它的左右子树也分别为二叉搜索树。

有1～n构建二叉搜索树，以i为根节点，左子树由[1, i - 1]构成，右子树由[i + 1, n]构成。

定义dp(x)为以[1, x]构成的二叉搜索树的数目。
n = 0, dp(0) = 0
n = 1, dp(1) = 1
n = 2, dp(2) = dp(0) * dp(1) + dp(1) * dp(0)
n = 3, dp(3) = dp(0) * dp(2) + dp(1) * dp(1) + dp(2) * dp(0)
dp(n) = dp(0) * dp(i - 1) +... + dp(k - 1) * dp(i - k) + dp(i - 1) * dp(0)

得到递推公式
dp[i] += (dp[j - 1]) * (dp[i - j]);

/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {
    var dp = Array(n + 1).fill(0)
    dp[0] = 1
    for(var i = 1; i <= n; i++){
        for(var j = 1; j <= i; j++){
            dp[i] += dp[j - 1] * dp[i - j]
        }
    }
    return dp[n]
};

这种求数量的题目一般都容易想到用动态规划的解法，这道题的模型正好是卡特兰数的定义，faster than 100%

image.png

/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {
    var res = 1
    if(n === 0) return res
    for(var i = 1; i <= n; i++){
        res = res * 2 * (2 * i - 1) / (i + 1)
    }
    return res
};