LeetCode.96 - 不同的二叉搜索树

• LeetCode - 96. 不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

思路

1. 《95 - 不同的二叉搜索树 II》 的简化版
2. 暴力做法: 沿用 95 代码，返回 length 即可（但运行时出现了 bad_alloc 的错误）
3. 可以直接用动态规划的思路解决此问题
4. dp[0] = 1, dp[1] = 1, dp[n + 1] = SUM(dp[i] * dp[n - i])

var numTrees = function (n) {
  const dp = new Array(n + 1).fill(1)
  for (let i = 0; i < n; ++i) {
    let sum = 0
    for (let j = 0; j <= i; ++j) {
      sum += dp[j] * dp[i - j]
    }
    dp[i + 1] = sum
  }
  return dp[n]
}