## 0096. Unique Binary Search Trees
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/unique-binary-search-trees/
## 思路
利用dp，每个格子存的是只有i个元素的binary search tree有多少种建树的可能性，那么
dp[0] = dp[1] = 1
dp[i] = dp[j-1]*dp[i-j] 对于每一个j，0<=j<=i
## Code

class Solution {
    public int numTrees(int n) {
        if(n == 1){
            return 1;
        }
        int[] dp = new int[n+1];
        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];
    }
}

## Result
Runtime: 0 ms, faster than **100.00%** of Java online submissions for Unique Binary Search Trees.
Memory Usage: 37.7 MB, less than **9.25%** of Java online submissions for Unique Binary Search Trees.