96. Unique Binary Search Trees（js）

96. Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?

Example:

Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:

   1         3     3      2      1
           /     /      /       
     3     2     1      1   3      2
    /     /                        
   2     1         2                 3
题意：给定一个数字，求出可以组成二叉搜索树的颗数
代码如下：

/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {
    var dp=[];
    for(var i=0;i<n+1;i++){
        if(i===0 || i===1){
            dp[i]=1;
        }else{
            dp[i]=0;
        }
    }
    for(var i=2;i<=n;i++){
        for(var j=0;j<i;j++){
            dp[i]+=dp[j]*dp[i-j-1];
        }
    }
    return dp[n];
};