96. 不同的二叉搜索树

题目描述

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

思路

在做过 95. 不同的二叉搜索树 II 之后，我们可以通过类似的回溯思想去计算，不过因为没有生成树的必要，因此我们可以记录 n 个节点可以生成多少种树，这样就可以减少计算量了。

再仔细想一想，这样的话，其实我们可以推导一下从 1 到 n 的树的数量。

• n=0 时 T(0) 为 1；
• 对于 n=1，只有一棵树；
• 对于 n=2，两个节点可以各自为根节点，可以划分处 T(1)+T(1)=2 棵树；
• 对于 n=3，三个节点互为根节点，划分出 T(2)T(0)+T(1)T(1)+T(0)T(2) 一共 5 棵树。

这样我们能推出节点为 n 时树的数量为 $T(n)={\sum }_{i=1}^{n}T(i-1)\times T(n-i)$

看上去这很像动态规划的转移方程，我们怎样去转换呢？在第一重循环的时候遍历 [1, i, n]，第二重循环遍历 [1, j, i]，那么这个时候 dp[i]=dp[j-1]*dp[i-j]。这样就可以一层一层地计算树的数量了。

最终代码：

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

想得太多