Question: https://oj.leetcode.com/problems/unique-binary-search-trees/
Question Name: Unique Binary Search Trees
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | class Solution: # @return an integer def numTrees(self, n): # numOfTrees[i] == j means for n is i, there are j unique # binary search trees for it. numOfTrees = [1, 1, 2] nextTrying = len(numOfTrees) while nextTrying <= n: # Comptute how many unique binary search trees are there for # n == nextTrying. count = 0 for center in xrange(nextTrying): # numOfTrees[center] is the number of unique binary search # trees in the left son # numOfTrees[nextTrying-center-1] is the number of unique # binary search trees in the right son # numOfTrees[center] * numOfTrees[nextTrying-center-1] is # the number of unique binary search trees with "center" # being the root. count += numOfTrees[center] * numOfTrees[nextTrying-center-1] numOfTrees.append(count) nextTrying += 1 return numOfTrees[n] |