一天一大 leet(三角形最小路径和)难度:中等-Day20200715

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

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

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

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

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