Skip to content

Instantly share code, notes, and snippets.

@bhaveshmunot1
Created June 4, 2020 03:45
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save bhaveshmunot1/4c12a67f1a1292e21f21c05ea7b6ff6c to your computer and use it in GitHub Desktop.
Leetcode #96: Unique Binary Search Trees
class Solution {
public:
int numTrees(int n) {
vector<int> dp(n+1);
dp[0] = 1;
dp[1] = 1;
for (int i=2; i<=n; i++) {
int sum = 0;
for (int k=1; k<=i; k++) {
sum += dp[k-1]*dp[i-k];
}
dp[i] = sum;
}
return dp[n];
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment