Untitled
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