Unique Binary Search Trees @ LeetCode (Python)
kitt
posted @ 2014年2月18日 12:22
in LeetCode
, 2136 阅读
动态规划, 节点数为0算一种情况, 即null。左、右子树节点共n-1个。左子树节点数从0走到n-1, 当左子树节点数为k时, 所有可能情况有dp[k] * dp[n-1-k]种。
class Solution:
# @return an integer
def numTrees(self, n):
dp = [0 for i in xrange(n+1)]
dp[0] = 1
for nodeNum in xrange(1, n+1):
for leftSubNum in xrange(nodeNum):
dp[nodeNum] += dp[leftSubNum] * dp[nodeNum - 1 - leftSubNum]
return dp[n]
评论 (0)