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.
1 3 3 2 1
\ / / / \
3 2 1 1 3 2
/ / \
2 1 2 3
題意：給定一個(gè)數(shù)字n千扔，那么用從1到n這些數(shù)字構(gòu)造一個(gè)二叉查找樹有多少種方法悯舟？
思路：
自己開始想的是用搜索的方法，即從1到n，嘗試以每個(gè)數(shù)字都作為根節(jié)點(diǎn)去構(gòu)造一個(gè)二叉查找樹弦撩，需要用一個(gè)數(shù)組來記錄當(dāng)前使用了哪些數(shù)字。但是有一個(gè)很難處理的地方是需要記錄當(dāng)前這棵樹的狀態(tài)荤西，這樣才能確定當(dāng)前搜索到的數(shù)字有幾種放置的方法祠饺。想了一下，這種搜索的方法時(shí)間復(fù)雜度非常高叽掘，應(yīng)該是階乘的級(jí)別楣铁。
最后想到應(yīng)該是動(dòng)態(tài)規(guī)劃的思路，但是沒想出來解法更扁，還是看了discuss的答案盖腕。n個(gè)數(shù)字情況下，從1到n每個(gè)數(shù)字都可以當(dāng)做根節(jié)點(diǎn)浓镜，用g(k,n)表示n個(gè)數(shù)字溃列，以k為根節(jié)點(diǎn)生成一個(gè)BST的方案個(gè)數(shù)，用t(n)表示n個(gè)數(shù)字生成BST的總方案數(shù)膛薛，則t(n) = g(1,n) + g(2,n) + ... + g(n,n)听隐，容易知道t(1) = 1,t(2) = 2。
假如n=4哄啄，k=2雅任，則k的左子樹只能由1來構(gòu)造风范，右子樹由3、4來構(gòu)造椿访，而用3乌企、4構(gòu)造和用1、2構(gòu)造的方案數(shù)其實(shí)是一樣的成玫，所以能夠得出g(2,4) = t(1) * t(2)，即g(k, n) = t(k-1) * t(n-k)拳喻，由此能夠推出t(n) = t(0) * t(n-1) + t(1) * t(n-2) + ... + t(n-1) * t(0)哭当，t(0)可設(shè)置為1.
public int numTrees(int n) {
if (n <= 1) {
return 1;
}
int[] nums = new int[n+1];
nums[0] = 1;
nums[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
nums[i] += nums[j - 1] * nums[i - j];
}
}
return nums[n];
}