96. 不同的二叉搜索树

Difficulty
Medium
Tags
动态规划
URL
https://leetcode-cn.com/problems/unique-binary-search-trees/
Star
❤
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
notion imagenotion image
输入：n = 3
输出：5
示例 2：
输入：n = 1
输出：1
提示：
  • 1 <= n <= 19
 

法1

思路
采用动态规划，难点在于寻找状态转移函数。
动态规划五部曲：
  1. dp数组：dp[i] 表示n=i时有dp[i]种二叉搜索树，所以，最后返回的是dp[n]
  1. 状态转移函数
      2. 当 n=2 时，显然有两种
      当 n=3 时， 有以下五种
      notion imagenotion image
      观察发现，五种由以下三类构成：
    1. 头节点为1的：左右分别有0，2 个节点。包含dp[0] * dp[2]种
    2. 头节点为2的： 左右分别有1，1个节点。包含dp[1] * dp[1]种
    3. 头节点为3的：左右分别有2，1个节点。 包含dp[2] * dp[0]种
      4. 那么可以类推，dp[i] += dp[j-1]* dp[i-j] ,j = [1,2,3,...,i]
      思路，让每个节点都当一次头节点，总共有n种头节点，将这n种累加起来就是总共种类。当第j个节点当头节点时，有dp[j-1] * dp[n-j]种。其中dp[j-1] 为左子树的情况，dp[n-j]为右子树的情况.
题解
class Solution:
    def numTrees(self, n: int) -> int:
        if n== 1:
            return 1
        dp = [0] * (n+1) 
        dp[0], dp[1], dp[2] = 1, 1, 2
        for i in range(3, n+1):
            for j in range(1, n+1):
                dp[i] += dp[j-1] * dp[i-j]
        return dp[n]