這道題使用動(dòng)態(tài)規(guī)劃解決
對(duì)于1...n的節(jié)點(diǎn)渗鬼，我們從中挑出一個(gè)節(jié)點(diǎn) i (1 <= i <=n)作為根節(jié)點(diǎn)阱持。在這種情況下荧嵌，所有的情況的總數(shù)是1...i-1和i+1...n的乘積小作，G(n) = G(i -1) * G(n - i)
在給定n的情況下台汇，結(jié)果是遍歷i從1到n的結(jié)果的總和。G(n) = G(0)G(n-1) + ...+G(i -1) * G(n - i) + ... G(n-1)G(0)
這個(gè)我們用腦子想想就知道
G(0) = 1;
G(1) = 1;
我們從n=2開始篱瞎，一步步往后算苟呐。代碼如下。
class Solution {
public int numTrees(int n) {
int[] data = new int[n + 1];
data[0] = 1;
data[1] = 1;
for(int i = 2; i <= n; i++){
int current = 0;
for(int j = 1; j <= i; j++){
current += data[j - 1] * data[i - j];
}
data[i] = current;
}
return data[n];
}
}
