問題：
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.
image.png
大意：
給出n芍锦，包含1~n這些節(jié)點(diǎn)可以形成多少個(gè)不同的BST（二叉查找樹）？
比如调塌，
給出n = 3逆害，有5個(gè)不同的BST：
image.png
思路：
二叉查找樹的性質(zhì)是左子節(jié)點(diǎn)一定小于父節(jié)點(diǎn)头镊，右子節(jié)點(diǎn)一定大于父節(jié)點(diǎn)。
我們思考一下可以發(fā)現(xiàn)魄幕，要形成不同的二叉樹相艇，最基本的分類是1n各自都做一次根節(jié)點(diǎn)。在它們作為根節(jié)點(diǎn)時(shí)纯陨，又分別還有多少種不同的組合方式呢坛芽？由于這是一個(gè)二叉查找樹，那么根節(jié)點(diǎn)的左邊一定都是小于他的數(shù)翼抠，右邊一定都是大于它的數(shù)咙轩，所以1n就會(huì)被分成兩部分去放置，這時(shí)候由可以分別把左子節(jié)點(diǎn)阴颖、右子節(jié)點(diǎn)分別看成要安放一部分?jǐn)?shù)字的根節(jié)點(diǎn)活喊，又變成了一樣的規(guī)律。
所以假設(shè)以i為根節(jié)點(diǎn)量愧，可能的組合情況為F（i钾菊，n），而G（n）為輸入n后的結(jié)果侠畔。則
F（i结缚，n） = G（i-1）*G（n-i）
也就是左子節(jié)點(diǎn)以下的可能數(shù)量乘以右子節(jié)點(diǎn)以下的可能數(shù)量。
而因?yàn)?~n都可能作為根節(jié)點(diǎn)软棺，所以最終的值是它們的和红竭，也就是
G（n） = F（1，n） + Ｆ（２，ｎ）∫鹣堋＋ ……∽畋＋Ｆ（ｎ，ｎ）
換算一下就是
Ｇ（ｎ）∠』稹＝∨凇Ｇ（０） * G（n-1） + G（1） * G（n-2） ＋ …… ＋ G（n-1） *Ｇ（０）
其中我們可以直接看出 Ｇ（０）』四＝∑谩Ｇ（１） ＝∩娜簟１达布。這個(gè)作為初始值來(lái)遞歸計(jì)算就可以了，要知道G（n）逾冬，我們必須把前面的數(shù)都計(jì)算出來(lái)黍聂。
代碼（Java）：
public class Solution {
public int numTrees(int n) {
int[] res = new int[n+1];
res[0] = 1;
res[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
res[i] += res[j-1] * res[i-j];
}
}
return res[n];
}
}
合集：https://github.com/Cloudox/LeetCode-Record
