yanshidong10123815
BAN USERI have resolved it here: oj.leetcode.com/problems/unique-binary-search-trees/
class Solution:
# @return an integer
def numTrees(self, n):
# c[i] is the count of different bts using 1...i
c = [0] * (n + 1)
c[1] = 1
for i in range(1, n + 1):
# the tree's root is j, left child may be 1...j-1, right child may be j+1...i
for j in range(1, i + 1):
if c[j - 1] * c[i - j] > 0:
# the count of bts using j+1...i is equal to using 1...i-j
c[i] += c[j - 1] * c[i - j]
elif c[j - 1] == 0:
c[i] += c[i - j]
elif c[i - j] == 0:
c[i] += c[j - 1]
return c[n]
It is like the problem "best time to buy and sell stock".
- yanshidong10123815 January 28, 2015