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

骑猪看日落 2023-08-17 15:14 44阅读 0赞

96. Unique Binary Search Trees

Medium

191974FavoriteShare

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：
    Distinguish between the two approaches,DP & memory recursion
    DP -->No store.Once operate need calculate all.
    memory recursion--> Store small value to calc larger one
    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))

Memory Recursion:

C++ version:

res is accumulative variable need += to accumulate

#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;
    //memory recursion
    class Solution
    {
    public:
        int numTrees(int n)
        {
            if(n==0) return 1;
            if(m_.count(n)) return m_[n];
            int res=0;
            for(int i=0;i<n;i++)
            {
                int left=numTrees(i);
                int right=numTrees(n-i-1);
                res+=left*right;
            }
            return m_[n]=res;
        }
    private:
        unordered_map<int,int> m_;
    
    };
    
    int main()
    {
        Solution s;
        cout<<s.numTrees(5)<<endl;
        return 0;
    }

Python version:
    Question:why init declare dp not directly put in numTrees???????????

class Solution(object):
        # class-->object def-->self
        # store
        def __init__(self):
            self.dp=dict()
    
        def numTrees(self,n):
            # judge
            if n in self.dp:
                return self.dp[n]
            # null
            if n==0 or n==1:
                return 1
            # store
            sum=0
            for i in range(1,n+1):
                sum+=self.numTrees(i-1)*self.numTrees(n-i)
            self.dp[n]=sum
            return sum

转载于:https://www.cnblogs.com/Marigolci/p/11362491.html