Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,Given n = 3, there are a total of 5 unique BST's.
給出一個(gè)數(shù)字n稚瘾，由從1到n這n個(gè)數(shù)字可以組成多少個(gè)結(jié)構(gòu)互異的二叉樹(shù)
對(duì)于一顆有n個(gè)節(jié)點(diǎn)的二叉樹(shù)，選定一個(gè)根節(jié)點(diǎn)玻淑，其左子樹(shù)和右子樹(shù)的數(shù)目會(huì)是：
(0,n-1)陵像、(1,n-2)、(2,n-3)......(n-1,0)
這就構(gòu)成了這個(gè)二叉樹(shù)所有互異的結(jié)構(gòu)你稚。
所以一個(gè)節(jié)點(diǎn)數(shù)目為n的二叉樹(shù)的互異的樹(shù)的數(shù)目為：
f(n) = f(0) * f(n-1) + f(1) * f(n-2) +......+f(n-1) * f(0)
var numTrees = function(n) {
var G = [];
G[0] = G[1] = 1;
for(var i=2; i<=n; i++) {
for(var j=1; j<=i; j++) {
if (G[i]===undefined)
G[i] = 0;
G[i] += G[j-1] * G[i-j];
}
}
return G[n];
};
