之前看算法導論時，講了給定幾個數(shù)字寸宏，能構(gòu)造出幾種二叉樹宁炫，當時只想到排列組合的解決方法，極其復雜又不好記氮凝，過段時間還忘了羔巢。。罩阵。竿秆。今天看大牛的文章，評論有人提及卡特蘭數(shù)稿壁，了解后才知道這么優(yōu)雅的解決思路幽钢。。
卡特蘭數(shù)前幾項
卡特蘭數(shù)前幾項為 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...
如果在解題時推出了前幾個數(shù)字符合這種規(guī)律的話傅是，就可以考慮是否用卡特蘭數(shù)求解了匪燕。
卡特蘭數(shù)的遞推公式
令 f(0) = 1 遞推式為 f(n) = f(0) * f(n-1) + f(1) * f(n-2) + ... + f(n-2) * f(1) + f(n-1) * f(0)。
這個式子是我們將問題與卡特蘭數(shù)聯(lián)系起來的思路喧笔。而求解就不要用這個式子了帽驯，數(shù)學家們想出了通用計算公式 f(n) = c[2n,n] - c[2n, n+1] = c[2n,n]/(n+1)。計算結(jié)果時书闸，還是用這個式子計算吧尼变。
卡特蘭數(shù)的應用
出棧問題
二叉樹構(gòu)成問題
凸多邊形的三角形劃分
括號匹配， 01 序列 等
