給出n個(gè)數(shù)字，能夠構(gòu)建出多少個(gè)不同的bst。
這道題可以用動(dòng)態(tài)規(guī)劃來做。那么動(dòng)態(tài)規(guī)劃重要的是找出狀態(tài)，以及狀態(tài)轉(zhuǎn)移方程。
我們來考慮一下狀態(tài)以及轉(zhuǎn)移，我們可以列舉出數(shù)組里面每一個(gè)數(shù)字i來當(dāng)bst的root，然后根據(jù)bst的性質(zhì)我們知道root左邊的都是比他小的，右邊都是比他大的。顯然，左子樹是用[1,i-1],右子樹是用[i+1,n]構(gòu)建的，那么我們會(huì)發(fā)現(xiàn)如果對(duì)于每一個(gè)i我們都這樣的去構(gòu)建這個(gè)問題就會(huì)轉(zhuǎn)移到左右子樹的構(gòu)建上去。于是我們就發(fā)現(xiàn)了狀態(tài)的轉(zhuǎn)移。但是這個(gè)轉(zhuǎn)移如何用數(shù)學(xué)的方法表示出來呢。
設(shè)G(n)為n個(gè)數(shù)字構(gòu)建出的bst總數(shù)，F(xiàn)(i,n)為n個(gè)數(shù)字，i為root的時(shí)候可以構(gòu)建的bst的數(shù)目。
那么我們仿佛找到了一個(gè)關(guān)系：
G(n) = F(1,n)+F(2,n)+...+F(n,n)
所以這個(gè)F關(guān)系式怎么轉(zhuǎn)化呢？
假設(shè)我們有[1,2,3,4,5,6]6個(gè)數(shù)，我選2為root，那么2的左邊有[1],右邊有[3,4,5,6]，所以[1]能構(gòu)建bst的數(shù)目是G(1),而[3,4,5,6]能構(gòu)建bst數(shù)目的是G(4)，為什么呢？因?yàn)槲覙?gòu)建bst主要的是看增序數(shù)組的元素個(gè)數(shù)跟元素具體是什么，是不是從1開始的并沒有什么關(guān)系.
于是：
F[2,6] = G(1)G(4);
F[i,n] = G(i-1)G(n-i);
所以這個(gè)G(n)就可以算了：
G(n) = G(0)G(n-1)+G(1)G(n-2)+...+G(n-1)*G(0)
G(0)=G(1) =1
于是這個(gè)狀態(tài)轉(zhuǎn)移方程我們也得出來了。
int dp[n+1];
dp[0]=dp[1]=1;
for(int i=2;i<=n;++i)
{
dp[i]=0;
for(int j=1;i<=i;++j)
dp[i] += dp[j-1]+dp[i-j];
}
return dp[n];
基本上按這翻譯的：https://discuss.leetcode.com/topic/8398/dp-solution-in-6-lines-with-explanation-f-i-n-g-i-1-g-n-i/17
