96. Unique Binary Search Trees

https://leetcode.com/problems/unique-binary-search-trees/

参考：

• http://bangbingsyb.blogspot.com/2014/11/leetcode-unique-binary-search-trees-i-ii.html

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {
  var count = [1, 1]

  for (let i = 2; i <= n; i++) {
    count[i] = 0
    for (let j = 0; j < i; j++) {
      count[i] += count[j] * count[i - j - 1]
    }
  }

  return count[n]
}

Python

class Solution(object):

    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        count = [1 if i <= 1 else 0 for i in range(n + 1)]
        for i in range(2, n + 1):
            for j in range(i):
                count[i] += count[j] * count[i - j - 1]
        return count[n]

Go

func numTrees(n int) int {
	count := make([]int, n+1)
	count[0] = 1
	count[1] = 1

	for i := 2; i <= n; i++ {
		for j := 0; j < i; j++ {
			count[i] += count[j] * count[i-j-1]
		}
	}

	return count[n]
}