python实现leetcode之96. 不同的二叉搜索树

解题思路

动态规划

对于元素数量是i的二叉搜索树
左子树的元素数量j，右子树的元素数量i-j-1，根1
total == i
方案树为j从0到i-1的所有情况下的组合，每一种的数量为dp[j] * dp[i-j-1]

96. 不同的二叉搜索树

代码

class Solution(object):
    def numTrees(self, n):
        dp = [0 for _ in range(n+1)]
        dp[0] = 1
        for i in range(1, n+1):
            for j in range(i):
                # 左子树的元素数量j，右子树的元素数量i-j-1，根1
                #total == i
                dp[i] += dp[j] * dp[i-j-1]
        # 当i是n时，就是答案
        return dp[n]