题解 | #有多少个不同的二叉搜索树#

1.思路

考虑$f(i)f(i)$表示第$ii$个节点作为根节点时所有二叉搜索树的可能，题目要求是求给定$nn$有多少种可能，即$dp(n)=f(1)+f(2)+\cdots +f(n)dp(n)=f(1)+f(2)+\backslash cdots\; +f(n)$。
我们知道，$f(i)=dp[i-1]\ast dp[n-i]f(i)=dp[i-1]*\; dp[n-i]$，即第$ii$个节点为根节点时，左节点有$i-1i-1$个，右节点有$n-in-i$个，$f(i)f(i)$即为左右节点所有二叉搜索树的可能的乘积。 现在结合两个式子，可以得出
$dp[n]=dp[0]\ast dp[n-1]+dp[1]\ast dp[n-2]+\cdots +dp[n-1]\ast dp[0]dp[n]=dp[0]*\; dp[n-1]\; +\; dp[1]*\; dp[n-2]\; +\; \backslash cdots\; +dp[n-1]\; *\; dp[0]$

2.代码实现

let n = ~~readline()

function main(n) {
    const dp = new Array(n + 1).fill(0)
    dp[0] = 1, dp[1] = 1
    for(let i = 2 ; i <= n ; i++) {
        for(let k = 1 ; k <= i ; k++) {
            dp[i] += dp[k-1] * dp[i - k]
        }
    }
    return dp[n]
}

console.log(main(n))