LeetCode 96. 不同的二叉搜索树

题目

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的二叉搜索树有多少种？返回满足题意的二叉搜索树的种数。

例：
输入：n = 3
输出：5

方法：动态规划

• dp[i] 记录由 i 个节点组成且节点值从 1 到 i 互不相同的二叉搜索树的种数，初始均为 0
• 由 0 个节点组成的二叉搜索树有一种，由 1 个节点组成的二叉搜索树有一种
• 循环遍历，记录从由 2 个节点组成的二叉搜索树到由 n 个节点组成的二叉搜索树的种树。因为根节点的值是不固定的，那么内层循环的参数 j 表示根节点的值，不同根节点产生的树种和即为最后的二叉搜索树的种数。而每个根节点所产生的二叉搜索树的种树，由其左子树的种树与右子树的种树的乘积得到

class Solution(object):
    def numTrees(self, n):
        dp = [0] * (n + 1)
        dp[0], dp[1] = 1, 1
        for i in range(2, n + 1):
            for j in range(1, i + 1):
                dp[i] += dp[j-1] * dp[i-j]
        return dp[n]

参考

代码相关：https://programmercarl.com/0096.%E4%B8%8D%E5%90%8C%E7%9A%84%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html