In this Leetcode Unique Binary Search Trees problem solution we have Given an integer n, return the number of structurally unique BST’s (binary search trees) which has exactly n nodes of unique values from 1 to n.
Problem solution in Python.
class Solution(object): def numTrees(self, n): """ :type n: int :rtype: int """ if n==0 or n==1: return 1 dp = [0]*(n+1) dp[0] = 1 dp[1] = 1 for i in range(2, n+1): for j in range(i): dp[i]+=dp[i-j-1] * dp[j] return dp[n]
Problem solution in Java.
public class Solution { public int numTrees(int n) { int[] record = new int[n+1]; record[0] = 1; record[1] = 1; return numTrees(n, record); } public int numTrees(int n, int[] record) { int result = 0; for(int i=1; i<=n; i++) { int tmp = 1; int left = i - 1; int right = n - i; if(record[left] > 0) { tmp *= record[left]; } else { tmp *= numTrees(left, record); } if(record[right] > 0) { tmp *= record[right]; } else { tmp *= numTrees(right, record); } result += tmp; } record[n] = result; return result; } }
Problem solution in C++.
class Solution { public: int numTrees(int n) { vector<int> dp(n+1, 0); dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; ++i) { for (int j = 0; j < i; j++) { dp[i] += dp[j] * dp[i-j-1]; } } return dp[n]; } };
Problem solution in C.
int solutions[1024]={1,1,}; int calculated = 1; int numTrees(int n) { if(n<calculated) return solutions[n]; int start = calculated+1; for(int loop = start;loop<n+1;loop++){ int sum = 0; for(int i=0;i<loop;i++){ sum += solutions[i]*solutions[loop-i-1]; } solutions[loop]=sum; } calculated = n; return solutions[n]; }