參考題解：
【算法】震驚！！！史上最詳細(xì)的卡特蘭數(shù)淺談！！！
卡特蘭數(shù)（好像很有用的說）

介紹

卡特蘭數(shù)是組合數(shù)學(xué)中一種著名數(shù)列，其前幾項(xiàng)為：

1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324,

通項(xiàng)式為：
$f(n)=\frac{C_{2n}^n}{n+1}=\frac{(2n)!}{(n+1)!n!}$
遞推式為：
$f(n)={\sum }_{i=0}^{n?1}f(i)?f(n?i?1)$
常用的是通項(xiàng)式變形：
$f(n)=C_{2n}^n?C_{2n}^{n?1}$

經(jīng)典問題：

一.01序列問題

給出一個(gè)n，要求一個(gè)長(zhǎng)度為2n的01序列，使得序列的任意前綴中1的個(gè)數(shù)不少于0的個(gè)數(shù)，
以下為長(zhǎng)度為6的序列:
111000 101100 101010 110010 110100

括號(hào)問題

矩陣鏈乘： P=a1×a2×a3×……×an，依據(jù)乘法結(jié)合律，不改變其順序，只用括號(hào)表示成對(duì)的乘積，試問有幾種括號(hào)化的方案？(h(n)種)

出棧次序問題

一個(gè)棧(無窮大)的進(jìn)棧序列為1,2,3,…n,有多少個(gè)不同的出棧序列?

多邊形劃分為三角形問題

將一個(gè)凸多邊形區(qū)域分成三角形區(qū)域的方法數(shù)?

給頂節(jié)點(diǎn)組成二叉樹問題

給定N個(gè)節(jié)點(diǎn)，能構(gòu)成多少種形狀不同的二叉樹？
　　先去一個(gè)點(diǎn)作為頂點(diǎn),然后左邊依次可以取0至N-1個(gè)相對(duì)應(yīng)的,右邊是N-1到0個(gè),兩兩配對(duì)相乘,就是h(0)*h(n-1) + h(2)*h(n-2) +…+ h(n-1)h(0)=h(n)（能構(gòu)成h(N)個(gè)）

例題：

洛谷1641 生成字符串
Loj10238網(wǎng)格
洛谷P2532 樹屋階梯
洛谷P3200 有趣的數(shù)列

總結(jié)

以上是生活随笔為你收集整理的卡特兰数（简单说说）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。