LeetCode开心刷题三十六天——96. Unique Binary Search Trees

发布时间：2020-12-14 05:09:52 所属栏目：大数据来源：网络整理

导读：96.?Unique Binary Search Trees Medium 1919 74 Favorite Share Given? n ,how many structurally unique?BST‘s?(binary search trees) that store values 1 ...? n ? Example: Input: 3Output: 5Explanation:Given n = 3,there are a total of 5 unique B

96.?Unique Binary Search Trees

Medium

Given?n,how many structurally unique?BST‘s?(binary search trees) that store values 1 ...?n?

Example:

Input: 3
Output: 5
Explanation:
Given n = 3,there are a total of 5 unique BST‘s:

   1         3     3      2      1
           /     /      /            3     2     1      1   3      2
    /     /                           2     1         2                 3
Three method solve this problem：
1.C++ version DP
mistake：
this part * + I misused.Cause large problem

dp[i] += dp[j] * dp[i - 1 - j];

#include<stdio.h>
#include<iostream>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<stack>
#include<climits>
#include<unordered_map>
#include<bits/stdc++.h>
//
using namespace std;

class Solution {
public:
    int numTrees(int n) {
        // how many trees if the total tree has dp[i] nodes.
        vector<int> dp(n + 1);
        dp[0] = dp[1] = 1;
        for (int i = 2; i < n + 1; i ++) {
            for (int j = 0; j < i; j++) {
                dp[i] += dp[j] * dp[i - 1 - j];
            }
        }
        return dp[n];
    }
};


int main()
{
    Solution1 s;
    cout<<s.Num(5)<<endl;
    return 0;
}

?DP python Version:

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

solu=Solution()
print(solu.numTrees(5))

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!