[LeetCode]96. 不同的二叉搜索树（Unique Binary Search Trees）

题目描述

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

示例:

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3

解题思路

动态规划。
假设第 n 个节点存在的二叉搜索树的个数为 $G(n)$，设 $f(i)$ 表示以 i 为根的二叉搜索树的数量，有：

$$G(n)=f(1)+f(2)+ \cdots +f(n)$$

而以 i 为根节点时，其种数等于左右子树的种数之积：

$$f(i)=G(i-1)\times G(n-i)$$

故：

$$G(n)=G(0)\times G(n-1)+G(1)\times G(n-2)+\cdots+G(n-1)\times G(0)$$

叫做卡特兰数。

代码

Python 3.6

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[0] = 1
        dp[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]

执行用时 : 80 ms
内存消耗 : 13.8 MB

参考

https://leetcode-cn.com/problems/unique-binary-search-trees/solution/hua-jie-suan-fa-96-bu-tong-de-er-cha-sou-suo-shu-b/