Untitled

 avatar
unknown
plain_text
a year ago
526 B
3
Indexable
class Solution { //ans depends on number of nodes, not on what's in those nodes
public:
    int solve(int n,vector<int>&dp){
        if(n==0 || n==1) return 1;

        if(dp[n]!=-1) return dp[n];
        int ans=0;
        for(int i=1;i<=n;i++){
            ans+=solve(i-1,dp) *solve(n-i,dp);
        }
        return dp[n]=ans;
    }
    int numTrees(int n) {
        vector<int> dp(n+1,-1); //nodes labelled 1 to n, dp[i] return no of unique BST when i nodes are present
        return solve(n,dp);
    }
};
Editor is loading...
Leave a Comment