96-Unique Binary Search Trees 二叉搜索树的数量

问题描述

链接：https://leetcode.com/problems/unique-binary-search-trees/description/

Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n.

解释：
给定一个整数n,求1～n,n个整数组成的二叉搜索树的个数

基本思想

构造长度为n+1的动态数组dp，其中dp[i] 表示 以i为中心的二叉搜索树的个数。假设
1～i个数中，

• 以1为为中心的，其左边有数0个，右边有树i-1个，所以以1为中心，i个数，可以构成二叉搜索树 dp[1]* dp[i-1]
• 以2为中心，其左边有数1个，右边有树i-2个，可以构成二叉搜索树为 左边1个数可以构成的二叉搜索树 乘上 右边 i-2个数可以构成的二叉搜索树
• ....
• 以i为中心，其左边有 i-1个数，右边有1个数，可以构成二叉搜索树的个数为 dp[i-1] * dp[1]
  将上面结果依次叠加，即得到1～i个数构成的二叉搜索树的数目
  时间复杂度 \(O(n^2)\) 需要计算3+4+....n次乘法

代码

C++

    int numTrees(int n) {
        if(n<=1) return 1;
        if (n<=2) return 2;
        vector<int> dp(n+1,0);
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for(int i=3;i<=n;++i) {
            int t = 0;
            for(int j=1;j<=i;++j) {
                t += dp[j-1] * dp[i-j];
            }
            dp[i] = t;
        }
        return dp[n];
    }

python

    def numTrees(self, n: int) -> int:
        if n <=0 : return 0
        if n<=1: return 1
        dp = [0] * (n+1)
        dp[0] = dp[1] = 1
        dp[2] = 2
        for i in range(3, n+1):
            for j in range(1,i+1):
              dp[i] += dp[j-1] * dp[i-j]
        return dp[n]