算法題面試題①-排列組合問題(母函數(shù)和卡特蘭數(shù))

母函數(shù)

對(duì)于一般的排列組合算法題, 可首先嘗試通過母函數(shù)來解決。

在數(shù)學(xué)中身笤，某個(gè)序列的母函數(shù)(Generating function结借，又稱生成函數(shù))是一種形式冪級(jí)數(shù)，其每一項(xiàng)的系數(shù)可以提供關(guān)于這個(gè)序列的信息鸦泳。使用母函數(shù)解決問題的方法稱為母函數(shù)方法。

母函數(shù)可分為很多種永品，包括普通母函數(shù)做鹰、指數(shù)母函數(shù)、L級(jí)數(shù)鼎姐、貝爾級(jí)數(shù)和狄利克雷級(jí)數(shù)钾麸。對(duì)每個(gè)序列都可以寫出以上每個(gè)類型的一個(gè)母函數(shù)。構(gòu)造母函數(shù)的目的一般是為了解決某個(gè)特定的問題炕桨，因此選用何種母函數(shù)視乎序列本身的特性和問題的類型饭尝。

母函數(shù)的兩個(gè)原則是:

把組合問題的加法法則和冪級(jí)數(shù)的乘冪對(duì)應(yīng)起來
母函數(shù)的思想就是把離散數(shù)列和冪級(jí)數(shù)一一對(duì)應(yīng)起來，把離散數(shù)列間的相互結(jié)合關(guān)系對(duì)應(yīng)成為冪級(jí)數(shù)間的運(yùn)算關(guān)系献宫，最后由冪級(jí)數(shù)形式來確定離散數(shù)列的構(gòu)造

普通母函數(shù)

我們先舉一個(gè)簡(jiǎn)單例子, 假設(shè)有1克钥平、2克、3克姊途、4克的砝碼各一枚涉瘾，請(qǐng)問我們能稱出哪幾種重量？每種重量各有幾種可能方案捷兰？

我們先來看看窮舉的過程立叛，先假設(shè)使用一個(gè)1g的砝碼，然后再假設(shè)在此情況下贡茅，使用2g的砝碼秘蛇，在此基礎(chǔ)上其做，再假設(shè)使用一個(gè)3g的，再假設(shè)使用一個(gè)4g的赁还，這就是第一中情況庶柿，這種方案稱出的重量為10g。

改變上面的一個(gè)假設(shè)條件秽浇，比如假設(shè)沒有使用4g的浮庐，只是用了1g、2g柬焕、3g审残，這種方案稱出的是6g，以此類推斑举，將所有的可能列舉出來后即可得到全部的方案搅轿。

在上述過程中, 每次對(duì)于1g的砝碼都有兩種情況，使用還是不使用富玷，其他的砝碼也一樣璧坟。因此每一種砝碼的狀態(tài)都可以有兩種砝碼狀態(tài)，以此類推總共就有2*2*2*2=16中方案赎懦，當(dāng)然其中包含一種一個(gè)砝碼也沒有的0g方案雀鹃。

我們最后可以窮舉出結(jié)果：1g、2g励两、8g黎茎、9g、10g各有一種方案当悔，3g傅瞻、4g、5g盲憎、6g嗅骄、7g各有兩種，總共十五種饼疙，這是在不算一種0g的方案的時(shí)候溺森，算上就是16種，和上面的過程相符宏多。

可以看到挑選不同種類砝碼之間是獨(dú)立的, 也就是說假如現(xiàn)在有1g和2g兩個(gè)砝碼, 所有可能狀態(tài)是, 其中||代表邏輯或, &&代表邏輯與, 每個(gè)用 “||”分開的一項(xiàng)都是一種方案儿惫≡璺＃“&&”表示同時(shí)滿足第一項(xiàng)和第二項(xiàng)的條件伸但。:

(使用1g&&使用2g) || (不使用1g&&使用2g) || (使用1g&&不使用2g) || (不使用1g&&不使用2g)

可以看出共有四種狀態(tài), 而這四種狀態(tài)可以概括為:

(使用1g || 不使用1g) && (使用2g || 不使用2g)

上面這個(gè)表達(dá)式與乘法表達(dá)式很像, 那么如果把“||”看成加法，“&&”看成乘法留搔，和多項(xiàng)式的乘法一模一樣更胖。題目需要的是幾種砝碼組合后的重量，是一個(gè)加法關(guān)系，但是在上式中“&&”是一種類似于乘法的運(yùn)算關(guān)系却妨。我們希望找到一種運(yùn)算關(guān)系饵逐，以乘法的形式運(yùn)算，但是結(jié)果表現(xiàn)出類似于加法的關(guān)系彪标。因此我們自然地想到可以用冪運(yùn)算來表達(dá)倍权。

$x^m\cdot x^n=x^{n+m}$

依然以1g和2g兩個(gè)砝碼進(jìn)行說明, 假如用, $x^1$ 表示1g砝碼, $x^2$ 表示2g砝碼, 注意冪指數(shù)代表是幾g砝碼。

那么之前的 (使用1g || 不使用1g) && (使用2g || 不使用2g) 這個(gè)條件就可以通過如下運(yùn)算式表示(我們之前提到過&&相當(dāng)于 $\cdot$ , ||相當(dāng)于+):
$(x^0+x^1)\cdot (x^0+x^2)$
注意上式中的 $x^0$ 代表不使用當(dāng)前砝碼, 因?yàn)槭褂?g砝碼就相當(dāng)于不使用砝碼捞烟”∩可以理解為, 本來在該放1g,2g,3g砝碼的地方放入了一個(gè) 0g 砝碼作為替換。所以就有:
$(x^0+x^1)\cdot (x^0+x^2)=x^0\cdot x^0+x^0\cdot x^1+x^0\cdot x^2+x^1\cdot x^2=x^0+x^1+x^2+x^3$
很顯然题画，有四種方案默辨，0g、1g苍息、2g缩幸、3g，結(jié)果與我們窮舉的結(jié)果相同竞思，而如果結(jié)果中有相同的項(xiàng)表谊，那么合并同類項(xiàng)后每一項(xiàng)的系數(shù)就是這種重量有幾種實(shí)現(xiàn)方案。我們現(xiàn)在用這種方法表示 1g,2g,3g,4g 四種砝碼的所有情況盖喷。
$(x^0+x^1)* (x^0+x^2) * (x^0+x^3)* (x^0+x^4)=x^0 + x^1 + x^2 + 2x^3 + 2x^4 + 2x^5 + 2x^6 + 2x^7 + x^8+ x^9 + x^{10}$

其中 $2x^3$ 代表由四種砝碼組合成3g砝碼共有兩種情況, 1g+2g和3g本身铃肯。注意 $2x^3$ 前面的系數(shù)2代表組成當(dāng)前砝碼質(zhì)量3共有2種不同組合方式。

接著我們把問題改一下, 求用1g传蹈、2g押逼、3g的砝碼稱出總重量小于10g的不同重量的方案數(shù)。這題乍看上去和之前沒區(qū)別, 不過需要注意的是, 此處砝碼是無(wú)限的惦界。那么我們?nèi)绾斡媚负瘮?shù)表達(dá)出無(wú)限這種性質(zhì)呢?

我們以2g砝碼為例挑格，因?yàn)槲覀冇袩o(wú)限個(gè)2g砝碼，所以我們可以把2個(gè)2g砝碼組合成一個(gè)4g砝碼沾歪，3個(gè)2g砝碼組合成一個(gè)6g砝碼漂彤，依次類推，我們光靠2g砝碼, 就可以擴(kuò)充我們已有的砝碼種類為 1g,2g,3g,4g,6g,8g,10g灾搏。如果我們按照這種方法接著對(duì)1g和3g砝碼做擴(kuò)充, 那么我們能得到從1g到10g的所有砝碼種類挫望。為何最大是10呢, 因?yàn)槲覀兇颂幰?guī)定了所有砝碼組合最大不超過10g, 那么超過10g的砝碼也就沒了意義, 所以我們只需要最大為10g的砝碼種類。

那么之前的公式就可以變?yōu)?( $\color{blue}{一般而言用1來替換下式中的x^0}$ ):

\begin{align}
&\qquad(1g砝碼的所有組合)\cdot(2g砝碼的所有組合)\cdot(3g砝碼的所有組合)\
&\
&=(x^0 +x^1 + x^2 + x^3 +\cdots+x^{10})\cdot(x0+x^2+x4+x^6+x8+x^{10})\cdot(x0+x^3+x6+x^9)\
\end{align}
將括號(hào)打開后所得的多項(xiàng)式的系數(shù)就是不同重量的組合方式狂窑。
現(xiàn)在我們來考慮一下 $\color{blue}{無(wú)限砝碼}$ 情況下的通項(xiàng)公式:
$\large(x^{v[0]*n_1[0]}+x^{v[0]*(n_1[0]+1)}+x^{v[0]*(n_1[0]+2)}+\cdots+x^{v[0]*n_2[0]})\\ \large(x^{v[1]*n_1[1]}+x^{v[1]*(n_1[1]+1)}+x^{v[1]*(n_1[1]+2)}+\cdots+x^{v[1]*n_2[1]})\\ \large\cdots\\ \large(x^{v[K]*n_1[K]}+x^{v[K]*(n_1[K]+1)}+x^{v[K]*(n_1[K]+2)}+\cdots+x^{v[K]*n_2[K]})$
其中(注意, 上邊是多項(xiàng)式的通項(xiàng)公式, 跟我們之前舉的例子沒有關(guān)系):
K對(duì)應(yīng)具體問題中物品的種類數(shù)媳板。
v[i]表示該乘積表達(dá)式第i個(gè)因子的權(quán)重，對(duì)應(yīng)于上訴問題為每個(gè)砝碼的的重量泉哈。
$n_1[i]$ 表示該乘積表達(dá)式第i個(gè)因子的起始系數(shù)蛉幸，對(duì)應(yīng)于具體問題中的每個(gè)物品的最少個(gè)數(shù)破讨，即最少要取多少個(gè)。
$n_2[i]$ 表示該乘積表達(dá)式第i個(gè)因子的終止系數(shù)奕纫，對(duì)應(yīng)于具體問題中的每個(gè)物品的最多個(gè)數(shù)提陶，即最多要取多少個(gè)。

假如我們現(xiàn)在題目是:給2張1元匹层，5張2元隙笆，3張5元，要得到15元升筏，有多少種組合仲器？

根據(jù)上述問題, 我們可以得到表達(dá)式:
$(1+x+x^2)(1+x^2+x^4+x^6+x^8+x^{10})(1+x^5+x^{10}+x^{15}+x^{20})$
我們注意到第一個(gè)多項(xiàng)式 $(1+x+x^2)$ , 其代表是有1元的所有組合的情況, 即為(0張1元 || 1張1元 || 2張1元)。因?yàn)槲覀兿喈?dāng)于是從0張1元開始, 到2張1元停止仰冠。所以我們此時(shí)有 $v[0]=1,\ n_1[0]=0,\ n_2[0]=2$ 乏冀。

以此類推, $(1+x^2+x^4+x^6+x^8+x^{10})$ 代表由2元組成的表達(dá)式, 故可表示 (0張2元 || 1張2元 || 2張2元 || 3張2元 || 4張2元 || 5張2元 ), 故此時(shí)有 $v[1]=2,\ n_1[1]=0,\ n_2[1]=5$

第三個(gè)表達(dá)式 $(x^5+x^{10}+x^{15}+x^{20})$ 是由5元組成, 故 $v[2]=5,\ n_1[2]=0,\ n_2[2]=4$

總結(jié)一下, $v$ ={1,2,5}, $n_1$ ={0,0,0}, $n_2$ ={2,5,4}。一般情況下 $n_1$ 都為0, 但也有特殊情況洋只。

$\LARGE 母函數(shù)例題$

$\large 求斐波那契數(shù)列的通項(xiàng)公式$
已知Fib(n)=Fib(n-1)+Fib(n-2), 這里假設(shè)Fib(1)=1,Fib(2)=1辆沦。因?yàn)镕ib(1)和Fib(2)都為1, 也就是說一次項(xiàng)和二次項(xiàng)的系數(shù)都為1, 那么根據(jù)如下三個(gè)求遞推公式的原則:

1.將遞推關(guān)系變成母函數(shù)方程
2.求解母函數(shù)方程
3.將母函數(shù)變成冪級(jí)數(shù)形式

我們首先寫出斐波那契數(shù)列的生成函數(shù)
$G(x)=x+x^2+2x^3+3x^4+5x^5+8x^6+\cdots\cdots$
等式兩邊同時(shí)乘 $x$ , 有:
$xG(x)=x^2+x^3+2x^4+3x^5+5x^6+8x^7+\cdots\cdots$
兩式相加, 有:
$G(x)+xG(x)=x+2x^2+3x^3+5x^4+8x^5+13x^6+\cdots\cdots$
我們對(duì)比 $G(x)$ , 可得:
$G(x)+xG(x)=\frac{G(x)}{x}-1$
所以我們可以得到:
$G(x)=\frac{x}{(1-x-x^2)}$
可以令: $1-x-x2=0$ , 得到兩根為: $a=\large\frac{1-\sqrt{5}}{2}$ , $b=\large\frac{(1+\sqrt{5})}{2}$ , 所以我們可以知道:
$1-x-x^2=(x-x_1)(x-x_2)=(1-ax)(1-bx)$

假設(shè) $\large\frac{x}{1-x-x^2}=\frac{m}{1-ax}+\frac{n}{1-bx}$ , 通分有: $x=m(1-bx)+n(1-ax)$ 。由系數(shù)關(guān)系可得 $m=-\frac{1}{\sqrt{5}},\ n=\frac{1}{\sqrt{5}}$ , 所以 $G(x)=-\frac{1}{\sqrt{5}(1-bx)}+\frac{1}{\sqrt{5}(1-ax)}$

我們可知:
$\frac{1}{(1-bx)}=\frac{1}{1-\frac{(1+\sqrt{5})}{2}x}$
是以公比為 $\large\frac{(1+\sqrt{5})}{2}$ 的等比數(shù)列识虚， $\large\frac{1}{(1-ax)}$ 是以公比為 $\large\frac{(1-\sqrt{5})}{2}$ 的等比數(shù)列肢扯，所以其通項(xiàng)公式為: $Fib(n)=\frac{1}{\sqrt{5}}(b^{n+1}-a^{n+1})$

$\large 砝碼組合$

若有1克、2克担锤、3克蔚晨、4克的砝碼各一枚，能稱出哪幾種重量肛循？各有幾種可能方案铭腕？

構(gòu)造母函數(shù)，如果用x的指數(shù)表示稱出的重量多糠，則：
1個(gè)1克的砝碼可以用函數(shù) $1+x$ 表示累舷，(前面的這個(gè)1表示1克的砝碼個(gè)數(shù)為0, 即 $x^0$ )
1個(gè)2克的砝碼可以用函數(shù) $1+x^2$ 表示，
1個(gè)3克的砝碼可以用函數(shù) $1+x^3$ 表示夹孔，
1個(gè)4克的砝碼可以用函數(shù) $1+x^4$ 表示被盈，

那么幾種砝碼的組合情況的用乘積表示有:
$( 1 + x ) \left( 1 + x ^ { 2 } \right) \left( 1 + x ^ { 3 } \right) \left( 1 + x ^ { 4 } \right) = 1 + x + x ^ { 2 } + 2 x ^ { 3 } + 2 x ^ { 4 } + 2 x ^ { 5 } + 2 x ^ { 6 } + 2 x ^ { 7 } + x ^ { 8 } + x ^ { 9 } + x ^ { 10 }$
其中系數(shù)即為方案數(shù)，譬如乘出重量為6的物品共有2種方案搭伤。

$\large 無(wú)限砝碼組合$

求用1分只怎、2分、3分的郵票貼出不同數(shù)值的方案數(shù)怜俐？
這個(gè)相對(duì)于上面的那個(gè)例子是：這個(gè)郵票可以重復(fù)身堡。可知其生成函數(shù)為:
$G ( x ) = \left( 1 + x + x ^ { 2 } + \ldots \right) \left( 1 + x ^ { 2 } + x ^ { 4 } + \ldots \right) \left( 1 + x ^ { 3 } + x ^ { 6 } + \ldots \right)$

$\large 德\cdot梅其里亞克稱重問題$

$\textbf{(1)}$ 重為 $a_1,a_2,a_3\ldots\ldots a_k$ 的砝碼, 如何放在天平的兩端, 記可稱重量為n的物體的不同方式為 $C_n$ , 則 $C_n$ 的母函數(shù)為:
$\large G ( x ) = \left( x ^ { - a_1 } + x^0 + x ^ { a_1 } \right) \left( x ^ { - a_2 } + x^0 + x ^ { a_2 } \right) \ldots \ldots \ldots \left( x ^ { - a_k } + x^0 + x ^ { a_k } \right)$
其中 $\large x^{-a_1}$ 表示砝碼a1和物體放在同一個(gè)托盤內(nèi), $\large x^{a_1}$ 表示砝碼和物體放在不同的托盤內(nèi), $\large x^0$ 則為用一個(gè)0g的砝碼代替, 即不用1g這個(gè)砝碼的意思佑菩。

$\textbf{(2)}$ 重為 $a_1,a_2,a_3\ldots\ldots a_k$ 的砝碼, 若只可以放在天平的一端, 記可稱重量為n的物體的不同方式為 $C_n$ , 則 $C_n$ 的母函數(shù)為:
$\large G ( x ) = \left( 1 + x ^ { a_1 } \right) \left( 1 + x ^ { a_2 } \right) \ldots \ldots \ldots \left( 1 + x ^ { a_k } \right)$

$\large 將整數(shù)分為若干小整數(shù)$

數(shù)的劃分盾沫，將整數(shù)分解為若干個(gè)整數(shù)(相當(dāng)于將n個(gè)蘋果放在n個(gè)無(wú)區(qū)別的盤子里裁赠，每個(gè)盤子可以放多個(gè)殿漠，也可以不放)

假設(shè)1出現(xiàn)的次數(shù)為記為 $a_1$ , 2出現(xiàn)的次數(shù)記為 $a_2\ldots\ldots$ 赴精。k出現(xiàn)的次數(shù)記為 $a_k$ ,那么生成函數(shù)為:
$G ( x ) = \left( 1 + x + x ^ { 2 } + x ^ { 3 } + \ldots \right) \left( 1 + x ^ { 2 } + x ^ { 4 } + x ^ { 6 }+ \ldots \right) \left( 1 + x ^ { 3 } + x ^ { 6 }+ \ldots \right) \cdots \left( 1 + x ^ { n } \right)$
前面的 $1 + x ^ { 2 } + x ^ { 4 } + x ^ { 6 } + x ^ { 8 } +\ldots$ 意思是當(dāng)出現(xiàn)一個(gè)2時(shí)為 $x^2$ ，當(dāng)出現(xiàn)兩個(gè)2時(shí)為 $x^4\ldots$

為什么當(dāng)出現(xiàn)n時(shí)绞幌，只有兩項(xiàng) $(1+x^n)$ , 因?yàn)槭菍?shù)n劃分為若干項(xiàng)蕾哟，所以不能超過該數(shù)，且由數(shù)1到n項(xiàng)數(shù)依次要 $<=\large\frac{n}{k},\ 其中(k=1.2,3,4...n)$

$\large 給定砝碼種類和相對(duì)應(yīng)的數(shù)量, 求出特定重量的組合方式$

#include <iostream>
#include<vector>  
using namespace std;  

int specificChoice(int query_value,const vector<pair<int,int> > &choices){ //接受兩個(gè)參數(shù), 一個(gè)是要查詢組合種類的數(shù)值, 一個(gè)是一個(gè)vector, vector中每個(gè)pair代表<砝碼重量, 該重量砝碼的數(shù)量>, <2,4>代表2g的砝碼有4個(gè)
    int maximum=0;
    for(auto &t:choices){
        maximum+=t.first*t.second;      //此處求出最高的冪次項(xiàng), 作為下面循環(huán)的停止條件莲蜘。
    }
    /*
    為了計(jì)算多項(xiàng)式, 我們首先要初始化一個(gè)vector用來存多項(xiàng)式的每個(gè)項(xiàng), 該vector的下標(biāo)指代的是冪, 值為該冪的項(xiàng)所對(duì)應(yīng)的系數(shù)谭确。即cumulative_coeff[2]=5代表x^2項(xiàng)的系數(shù)為5, 即5x^2
    */
    vector<int> cumulative_coeff(maximum+1,0);  //注意此處maximum也要取到, 所以初始化的大小要加一
    vector<int> temp(maximum+1,0);
    cumulative_coeff[0]=1;     //我們此處需要把砝碼重量為0的值初始化為1, 因?yàn)楹髞淼夹枰獜脑撎庨_始, 后續(xù)的計(jì)算方式都是以此作為基礎(chǔ)
        /*        
        假設(shè)我們有1g,2g,3g砝碼各一個(gè), 故有多項(xiàng)式為(1+x)(1+x^2)(1+x^3), 我們首先說明, 作為最外層循環(huán), i是用來以每個(gè)多項(xiàng)式為基本單位來遍歷的, 即(1+x),(1+x^2)和(1+x^3)這三個(gè)多項(xiàng)式, 故i遍歷三次。實(shí)際上i的遍歷次數(shù)取決于我們傳入的物品種類數(shù)目
        既然i指代的每個(gè)具體的表達(dá)式, j相當(dāng)于是遍歷上一輪得到的cumulative_coeff的結(jié)果的, 然后在j的循環(huán)中, 還有一個(gè)k的循環(huán), k是用來遍歷當(dāng)前多項(xiàng)式中每個(gè)元素的票渠。
        因?yàn)?1+x)(1+x^2)(1+x^3)最終最高次冪是6, 所以在經(jīng)過初始化后, 我們的cumulative_coeff列表為:
            1 0 0 0 0 0 0
        我們開始第一輪迭代, 當(dāng)i=0時(shí), 我們遍歷第一個(gè)多項(xiàng)式(1+x), 然后我們現(xiàn)在需要把這個(gè)(1+x)累加到cumulative_coeff中, 那么我們就對(duì)cumulative_coeff整個(gè)用j遍歷一遍逐哈。在每一輪遍歷j的過程中, 我們用k來遍歷當(dāng)前(1+x)這個(gè)多項(xiàng)式, 并將其累加到j(luò)遍歷到的地方
            
            當(dāng)j=0時(shí), 相當(dāng)于選擇cumulative_coeff[0], 
                當(dāng)k=0時(shí), 即代表選擇了(1+x)中的1, temp[k+j]+=(cumulative_coeff[0]=1)
                當(dāng)k=choices[i].first=1時(shí), 即代表選擇了(1+x)中的x, temp[k+j]+=temp[0+1]=(cumulative_coeff[0]=1) , 這就是用temp的意義, 不會(huì)重復(fù)+=, 否則如果直接在cumulative_coeff上做+=的話每次就重復(fù)計(jì)算了

            當(dāng)j=1時(shí), 相當(dāng)于選擇cumulative_coeff[1],
                當(dāng)k=0時(shí), 即代表選擇了(1+x)中的1, temp[1]+=(cumulative_coeff[1]=0)    在上一輪j=0中temp[1]已經(jīng)被加為1了, 在此輪加0
                當(dāng)k=choices[i].first=1時(shí), 即代表選擇了(1+x)中的x, temp[2]=cumulative_coeff[1]=0
            
            當(dāng)j=2,3,4,5,6時(shí), 因?yàn)閏umulative_coeff[j]=0, 所以對(duì)應(yīng)的temp[j+k]+=0
            ......
            在遍歷完所有的j后, 將temp上的值賦給cumulative_coeff, 注意不是+=而是=, 然后將temp所有元素重新初始化為0

            此時(shí)cumulative_coeff為:
            1 1 0 0 0 0 0

        開始第二輪迭代, 當(dāng)i=1時(shí), 我們遍歷第而個(gè)多項(xiàng)式(1+x^2), 然后我們現(xiàn)在需要把這個(gè)(1+x^2)累加到上一輪的cumulative_coeff中, 注意此處是1g,2g,3g砝碼各一個(gè), 如果不止一個(gè)的話k的最大值就不止是1:
             當(dāng)j=0時(shí), 相當(dāng)于選擇cumulative_coeff[0], 
                當(dāng)k=0時(shí), 即代表選擇了(1+x^2)中的1, temp[k+j]+=1   注意temp在上一輪結(jié)束的時(shí)候已經(jīng)全部初始化為0, 所以此處結(jié)果是temp[0]=1
                當(dāng)k=choices[i].first=2時(shí), 即代表選擇了(1+x^2)中的x^2, temp[k+j]+=(cumulative_coeff[0]=1) , 故temp[2]=1
        ......
        */
    for(int i=0;i<choices.size();i++){
        for(int j=0;j<=maximum;j++){
            for(int k=0;k+j<=maximum && k/choices[i].first<=choices[i].second;k+=choices[i].first){
                temp[k+j]+=cumulative_coeff[j];
            }
        }
        for(int j=0;j<=maximum;j++){
            cumulative_coeff[j]=temp[j];
            temp[j]=0;
        }
        cout<<"After finish<"<<choices[i].first<<","<<choices[i].second<<">: ";
        for(int co=0;co<=maximum;co++){     //每一輪結(jié)束后輸出本輪累加的cumulative_coeff, 便于理解
            cout<<cumulative_coeff[co]<<" ";
        }
        cout<<endl;
    }
    /*
    如果要求的問題是, 求最小的不能由這些砝碼組成的重量是多少, 只需要把return替換為:
    for(i=0;i<=maximum;i++{
        if(value[i]==0){
            return i;
        }
    }
    return -1;
    */
    return cumulative_coeff[query_value];
}

int main()  
{    
    vector<pair<int,int> > inputs;
    //給定3個(gè)2g的砝碼, 4個(gè)3g的砝碼, 2個(gè)5g的砝碼
    inputs.push_back({2,3});
    inputs.push_back({3,4});
    inputs.push_back({5,2});
    //求解用這些砝碼得到總重量為28g的所有可能組合數(shù)量
    cout<<specificChoice(28,inputs)<<endl;
    return 0;  
}

$\large 整數(shù)劃分問題$

將正整數(shù)n表示成一系列正整數(shù)之和: $n=n_1+n_2+\ldots+n_k$ , 其中 $n_1\geq n_2\geq\ldots\geq n_k,\quad k\geq1$ 。
正整數(shù) $n$ 的這種表示稱為正整數(shù) $n$ 的劃分问顷。求正整數(shù)n的不同劃分個(gè)數(shù)昂秃。
例如正整數(shù)6有如下11種不同的劃分:
6
5+1
4+2 4+1+1;
3+3 3+2+1 3+1+1+1;
2+2+2 2+2+1+1 2+1+1+1+1;
1+1+1+1+1+1

現(xiàn)在就是無(wú)限砝碼問題了, 設(shè)置一個(gè)最大上界為正整數(shù)n, 然后只要小于等于n的數(shù), 其每個(gè)數(shù)都可以被選用無(wú)數(shù)次。假設(shè)正整數(shù)n為6, 則我們有1,2,3,4,5,6這6個(gè)砝碼, 每個(gè)都有無(wú)限的數(shù)量, 僅僅要求不同砝碼組合的總重量小于整數(shù)n杜窄。

那么我們可以對(duì)上面的稍加變形

int infiniteChoice(int NUM){
        vector<int> cumulative_coeff(NUM+1,0);
        vector<int> temp(NUM+1,0);
        cumulative_coeff[0]=1;
        /*
        注意i要從1開始加起, 如果i是0的話, 底下的k+=i就會(huì)一直是k+=0, 就會(huì)陷入死循環(huán), 而且因?yàn)槲覀冎粚?duì)0g砝碼做了初始化, 所以本來也要從1g砝碼開始考慮肠骆。
        之所以上面那個(gè)代碼i是從0開始加起, 是因?yàn)樵谘h(huán)中, k+=choices[i].first 。choices[i].first一般來說不為0塞耕。
        
        總體來說我們所要做的改動(dòng)就是, i的上界變?yōu)榱薔UM, 因?yàn)橹灰∮贜UM的所有砝碼都是有無(wú)限個(gè)的, 所以產(chǎn)生的多項(xiàng)式是:
          (1+x+x^2+x^3+...)(1+x^2+x^4...)(1+x^3+x^6...)......(1+x^n)
        第二個(gè)改動(dòng)是, k不再被砝碼的數(shù)量所限制了, 每一輪循環(huán)的限制條件變?yōu)榱藘H剩 k+j<=NUM蚀腿。而且k每一輪也從 k+=choices[i].first變?yōu)榱薻+=1, 因?yàn)楝F(xiàn)在i就指代砝碼重量本身, 畢竟現(xiàn)在的砝碼重量種類是從1到n一個(gè)連續(xù)的序列。
        其他就沒什么改動(dòng)了
        */
        for(int i=1;i<=NUM;i++) 
        {   
            for(int j=0; j<=NUM; j++){   
                
                for(int k=0; k+j<=NUM; k+=i)  
                {  
                    temp[j+k] += cumulative_coeff[j];  
                } 
            } 
            for(int j=0; j<=NUM; ++j){    
                cumulative_coeff[j] = temp[j];  
                temp[j] = 0;  
            }  
        }  
        return cumulative_coeff[NUM]; 
}

卡特蘭數(shù)

我們首先來看一個(gè)例子, 假如現(xiàn)在有 n 個(gè)+1 和 n個(gè)-1, 總計(jì)2n個(gè)數(shù), 要用其組成一個(gè)序列 $a _ { 1 }, a _ { 2 } \dots \dots a _ { n }$ , 要求在序列中任何一點(diǎn)k上, 都有 $a _ { 1 } + a _ { 2 } + \ldots + a _ { k } \geq 0$ , 其中 $0 \leq k \leq 2 n$ 扫外。換句話說, 即:
序列1: 1 1 -1 -1 1 ...
序列2: 1 -1 1 -1 -1 ...
序列1看上去是暫時(shí)沒錯(cuò)的, 因?yàn)闊o(wú)論在哪個(gè)位置, 該位置之前(包括該元素)的元素和都大于等于0, 而序列2不是, 所以序列二不滿足要求

我們滿足上述要求的 $\color{blue}{序列的數(shù)量}$ 稱為卡特蘭數(shù) $C_n$ , 假設(shè)我們?cè)O(shè)不滿足上述要求的序列的數(shù)量為 $U_n$ , 那么 $C_n+U_n$ 就等于n 個(gè)+1 和 n個(gè)-1 的 $\color{blue}{所有排列組合}$ 的數(shù)量莉钙。

這個(gè)所有排列組合的數(shù)量如果用排列組合來表示即為 $\large C_{2n}^n\small=\left( \begin{array} { c } { 2 n } \\ { n } \end{array} \right)$ , 怎么理解這個(gè)呢?

我們可以理解為, 假設(shè)現(xiàn)在有一個(gè)長(zhǎng)度為2n的空的插槽, 我們從這2n個(gè)插槽中選出n個(gè)插槽, 插入n個(gè)+1, 那么剩下的插槽自然都是-1了。故為 $\large C_{2n}^n\small=\left( \begin{array} { c } { 2 n } \\ { n } \end{array} \right)$ 筛谚。注意此處的 $C_{2n}^n$ 與卡特蘭數(shù)的表示 $C_n$ 沒有什么關(guān)系, 只是都用 $C$ 來表示而已胆胰。

那我們現(xiàn)在有了 $C_n+U_n=\left( \begin{array} { c } { 2 n } \\ { n } \end{array} \right)$ , 下一步就是要求 $U_n$ 了。

我們假設(shè)有一個(gè)最小的k令 $a _ { 1 } + a _ { 2 } + \ldots + a _ { k } < 0$ , 由于此處k是最小的, 所以必有 $a _ { 1 } + a _ { 2 } + \dots + a _ { k - 1 } = 0,\quad a_k=-1$ , 并且k是一個(gè)奇數(shù)刻获。為了幫助理解, 我們假設(shè)現(xiàn)在有如下這個(gè)不滿足要求的序列(n=7):
1 -1 1 1 -1 -1 1 -1 -1 1 1 1 -1 -1
那么這個(gè)最小的k等于多少呢, 等于9(下標(biāo)從1開始算), 即在 $a_9$ 之前, 序列為:
1 -1 1 1 -1 -1 1 -1
其和為剛好為0, 加上 $a_9$ 后, 即加上-1, 其和即為-1了, 而且此時(shí) $k=9$ 也是奇數(shù)蜀涨。此時(shí)我們將前 $k=9$ 項(xiàng)(包括第k項(xiàng))的-1變?yōu)?, 1變?yōu)?1, k后面的序列不變, 那么上述序列變?yōu)?
-1 1 -1 -1 1 1 -1 1 $\color{red}{1}$ 1 1 1 -1 -1
很顯然, 此時(shí)整個(gè)序列中有8個(gè)+1, 有6個(gè)-1。(因?yàn)榘言瓉硎?1的n變?yōu)榱?1, 所以+1數(shù)量加一, -1數(shù)量減一)蝎毡。而最初的序列有7個(gè)+1和7個(gè)-1, 故當(dāng)時(shí)n=7厚柳。所以在改變后, 現(xiàn)在有n+1個(gè)+1, 有n-1個(gè)-1。

擴(kuò)展來說, 所有不滿足卡特蘭數(shù)條件的序列, 其經(jīng)過翻轉(zhuǎn)前k項(xiàng)后都會(huì)導(dǎo)致整個(gè)2n序列變?yōu)榘琻+1個(gè)+1和n-1個(gè)1, 那么換個(gè)角度來看, 是否只要滿足一個(gè)2n序列, 只要其包含n+1個(gè)+1和n-1個(gè)-1, 其所有的排列組合就等價(jià)于所有不滿足卡特蘭數(shù)序列的2n序列沐兵。換句話說, 包含n+1個(gè)+1和n-1個(gè)-1的序列的任何排列組合方式, 都可以將其按上述的方式反向翻轉(zhuǎn), 得到一個(gè)最小k元素, 滿足 $a _ { 1 } + a _ { 2 } + \ldots + a _ { k } < 0$ 别垮。那么這么一來, 不滿足卡特蘭數(shù)列條件的2n序列就 $\color{blue}{等價(jià)于}$ 一個(gè)包含n+1個(gè)+1和n-1個(gè)-1的2n序列。如果覺得此處證明不嚴(yán)謹(jǐn)請(qǐng)查閱編程之美4.3扎谎。

那么很顯然, 其就是我們要找的 $U_n$ 序列, 故 $U_n=\left( \begin{array} { c } { 2 n } \\ { n+1 } \end{array} \right)$ , 即相當(dāng)于從2n個(gè)插槽中選出n+1個(gè)插入+1或是n-1個(gè)插入-1, 注意其中 $C_{2n}^{n+1}=C_{2n}^{n-1}$ 碳想。

因此我們就有 (其中 $\left( \begin{array} { c } { 2 n } \\ { n } \end{array} \right)=\large\frac{(2n)!}{n!n!}$ ) :
$C_n=\left( \begin{array} { c } { 2 n } \\ { n } \end{array} \right)-U_n=\left( \begin{array} { c } { 2 n } \\ { n } \end{array} \right)-\left( \begin{array} { c } { 2 n } \\ { n+1 } \end{array} \right)= \left( \begin{array} { c } { 2 n } \\ { n } \end{array} \right) - \frac { n } { n + 1 } \left( \begin{array} { c } { 2 n } \\ { n } \end{array} \right)=\frac { 1 } { n + 1 } \left( \begin{array} { c } { 2 n } \\ { n } \end{array} \right) = \frac { ( 2 n ) ! } { ( n + 1 ) ! n ! }$
這就是我們要求的卡特蘭數(shù)的公式, 根據(jù)上式可得其遞推公式為:
$\mathrm { C } _ { 0 } = 1 \quad , \quad C _ { n + 1 } = \frac { 2 ( 2 n + 1 ) } { n + 2 } C _ { n }$
同時(shí), 其還有如下性質(zhì)(注意等式左邊是 $C_{\color{blue}{n+1}}$ 而右邊的項(xiàng)是 $C_{\color{blue}{n-i}}$ ):
$C _ { \mathrm { 0 } } = 1 \quad , \quad C _ { n + 1 } = \sum _ { i = 0 } ^ { n } C _ { i } C _ { n - i } \quad n \geq 0$
以及:
$C _ { n } = \frac { 1 } { n + 1 } \sum _ { i = 0 } ^ { n } \left( \begin{array} { l } { n } \\ { i } \end{array} \right) ^ { 2 }$
而其增長(zhǎng)趨勢(shì), 即復(fù)雜度為:
$C _ { n } \sim \frac { 4 ^ { n } } { n ^ { \frac { 3 } { 2 } } \sqrt { \pi } }$

$\Large 卡特蘭數(shù)的應(yīng)用(下面的C_n都代表卡特蘭數(shù))$

$\large 1.\ 入棧出棧$
我們可以把+1看為入棧, 而-1看做是出棧, 不能對(duì)一個(gè)空棧做出棧操作, 也就是說在每次出棧操作時(shí), 要確保棧中元素大于0烧董。換句話說, 也就是說對(duì)于序列中任意一個(gè)元素, 都有 $a _ { 1 } + a _ { 2 } + \ldots + a _ { k } \geq 0$ 。假設(shè)我們有n個(gè)數(shù), 其入棧和出棧的排列總數(shù)為 $C_n$ , 例如1,2,3入棧的出棧排序有123胧奔，132逊移，213，231和321五種龙填。

$\large 2.\ 括號(hào)匹配問題$
如上文所說胳泉，對(duì)于任意的k，前k個(gè)元素中-1的個(gè)數(shù)小等于+1的個(gè)數(shù)的序列計(jì)數(shù)岩遗，我們可以不停地變換形式扇商，比如將-1看成右括號(hào)，+1看成左括號(hào)宿礁，就變成了合法括號(hào)表達(dá)式的個(gè)數(shù)案铺。比如2個(gè)左括號(hào)和2個(gè)右括號(hào)組成的合法表達(dá)式有 $C_2 = 2$ 種, 是 ()() 和 (()) 。也就是說')'不能先于'('出現(xiàn), 即')'出現(xiàn)時(shí)前面一定要有一個(gè)'('與其匹配梆靖。

既然如上一點(diǎn)都把括號(hào)加上去了控汉，那么順便就再次轉(zhuǎn)換，n+1個(gè)數(shù)連乘涤姊，乘法順序有 $C_n$ 種暇番。或者更常見的, 三個(gè)矩陣連乘, 不過因?yàn)榫仃嚪铣朔ńY(jié)合率, 所以跟三數(shù)連乘沒什么區(qū)別思喊。

因?yàn)楸热缥覀內(nèi)齻€(gè)數(shù)連乘abc壁酬，那么等于在式子上加括號(hào)，有2種乘法順序恨课，分別是 $(ab)c$ 和 $a(bc)$ 舆乔。

我們?cè)偃為3來看看, 注意此處n指的是'('或')'單括號(hào)的數(shù)量，n為3的時(shí)候就是4個(gè)數(shù)相乘了剂公，那么我們?cè)O(shè)為abcd希俩，最初的標(biāo)號(hào)定在a上，我們對(duì)于n為3得到合法的括號(hào)序列有5個(gè)纲辽，分別是：((()))颜武，()(())，()()()拖吼，(())()和(()())鳞上，那么我們將一個(gè)左括號(hào)看成是當(dāng)前操作數(shù)指針往右移動(dòng)一個(gè)位置，一個(gè)右括號(hào)看成是當(dāng)前操作數(shù)和左邊最近的一塊操作數(shù)相乘起來吊档，那么對(duì)應(yīng)的五個(gè)表達(dá)式就是：a(b(cd))篙议，(ab)(cd)，((ab)c)d，(a(bc))d和a((bc)d)鬼贱，他們之間是一一對(duì)應(yīng)關(guān)系移怯。

$\large 3.\ 二叉搜索樹問題$
n個(gè)節(jié)點(diǎn)的二叉搜索樹的所有可能形態(tài)數(shù)為 $C_n$ 。注意是二叉搜索樹, 即左子節(jié)點(diǎn)比父節(jié)點(diǎn)小, 右子節(jié)點(diǎn)比父節(jié)點(diǎn)大这难。

假設(shè)我們現(xiàn)在有一個(gè)有序序列[1,2,3,4,5,6,7,8], 問總共能組成多少種不同的二叉搜索樹舟误。為了能得到所有可能二叉樹的情況, 我們需要遍歷這個(gè)序列, 將序列中每個(gè)元素分別當(dāng)做一次根節(jié)點(diǎn)。

假設(shè)我們現(xiàn)在選擇了下標(biāo)為2的元素3(下標(biāo)從0開始)作為根節(jié)點(diǎn), 那么此時(shí)該根節(jié)點(diǎn)的左子樹和右子樹中包含的節(jié)點(diǎn)是不是確定的? 注意是二叉搜索樹, 所以{1,2}落在了左子樹, {4,5,6,7,8}落在了右子樹雁佳。

而且此時(shí)左子樹和右子樹的排列方式是相互獨(dú)立的, {1,2}有2中方式組成一個(gè)二叉搜索樹, {4,5,6,7,8}有42種方式(先不用管這個(gè)是怎么得到的)組成一個(gè)二叉搜索樹年柠。那么, 此時(shí)當(dāng)以3作為根節(jié)點(diǎn)時(shí), 所有子樹的可能情況總和就是
$2\cdot42=84$
再次重申, 左子樹和右子樹是相互獨(dú)立的, 所以兩者的排列組合相當(dāng)于是笛卡爾積, 所以是2*42=84相乘奖磁。

我們?cè)賮硭伎家幌? 當(dāng)以3作為根節(jié)點(diǎn)將序列分為{1,2}和{4,5,6,7,8}以及當(dāng)以6作為根節(jié)點(diǎn)將序列分為{1,2,3,4,5}和{7,8}時(shí), 其結(jié)果是否是一樣的呢? 其實(shí)兩者最后的結(jié)果是一樣的, 都是84堂鲜。

那么, 這說明了, 當(dāng)一個(gè)根節(jié)點(diǎn)把一個(gè)有序數(shù)列(注意有序這個(gè)條件)分成左右兩個(gè)子樹時(shí), 分到子樹中的元素的值不重要, 即{1,2}和{7,8}兩者沒什么區(qū)別, 重要的是分到子樹中的元素的數(shù)量拯腮。即只要分到左子樹或右子樹中2個(gè)元素, 那么無(wú)論這兩個(gè)元素是{1,2},{3,4}還是{5,6}, 其最終該子樹的排列組合數(shù)量都是2篱蝇。

那么[1,2,3,4,5,6,7,8]這個(gè)序列可能產(chǎn)生的所有可能BST(二叉搜索樹)的數(shù)量就等于令序列中每一個(gè)元素為根節(jié)點(diǎn)時(shí), 左子樹乘右子樹得到的笛卡爾積, 即像2*42=84那樣凳枝。

我們把這個(gè)過程抽象一下, 假設(shè)我們現(xiàn)在用第i個(gè)元素將序列分成左右兩個(gè)序列, 該左右兩個(gè)序列是不是又可以分別被當(dāng)成新的序列, 遞歸地再分別被分成兩半沪铭。而且就像我們上面證明的, 分成兩半時(shí)每個(gè)序列中元素本身值不重要, 序列中每個(gè)元素的數(shù)量才重要, 那么我們就可以得出如下遞推公式:
$C _ { n } = \sum _ { i = 0 } ^ { n - 1 } C _ { i } C _ { n - 1 - i }$
其中 $C_i$ 代表該序列中包含i個(gè)元素, $C_{n-i-1}$ 代表其包含n-1-i個(gè)元素, 注意因?yàn)槊恳惠喰枰獙?dāng)前作為根節(jié)點(diǎn)的節(jié)點(diǎn)排除在外, 所以此處是n-1-i髓迎。假如序列長(zhǎng)度為n=8, i=2時(shí), 即相當(dāng)于用從左往右數(shù)第3個(gè)元素(i是從下標(biāo)0開始的)作為根節(jié)點(diǎn), 那么此處左子樹就有i=2個(gè)節(jié)點(diǎn), 右子樹就有8-1-2=5個(gè)節(jié)點(diǎn)旱易。注意此處有個(gè)trick, 因?yàn)槲覀冚斎氲膎=8, 所以當(dāng)我們用n-1的時(shí)候就自動(dòng)將當(dāng)前根節(jié)點(diǎn)排除在外了禁偎。即n-1-i跟 $\sum$ 的上界是n-1沒直接關(guān)系, $\sum$ 的上界是用來從0到n-1遍歷這n個(gè)元素, 分別用其作為根節(jié)點(diǎn)。

那么 $C_i$ 和 $C_{n-1-i}$ 怎么求呢, 此時(shí)需要將分到左子樹和右子樹的序列分別當(dāng)做新的輸入序列, 重新開始遞歸求解阀坏。

我們看上述遞推公式, 再與卡特蘭數(shù)的遞推公式對(duì)比一下:
$C _ { n + 1 } = \sum _ { i = 0 } ^ { n } C _ { i } C _ { n - i } \quad 和 \quad C _ { n } = \sum _ { i = 0 } ^ { n - 1 } C _ { i } C _ { n - 1 - i }$

會(huì)發(fā)現(xiàn)唯一的區(qū)別就是用n-1替換為了n, 也就是說, 其就是卡特蘭數(shù), 那么此時(shí)我們可以直接使用卡特蘭數(shù)的公式求解如暖。
$C _ { 0 } = 1 , \quad C _ { n + 1 } = \frac { 2 ( 2 n + 1 ) } { n + 2 } C _ { n }$
即:

long C=1;
for(int i=0;i<n;i++){
    C = C * 2 * (2 * i + 1) / (i + 2);
}

其中n代表序列的長(zhǎng)度。

$\large 4.\ 走方格問題$
對(duì)于一個(gè)n*n的正方形網(wǎng)格忌堂，每次我們能向右或者向上移動(dòng)一格盒至，而且不能越過對(duì)角線。那么從左下角到右上角的所有在副對(duì)角線右下方的路徑總數(shù)為 $C_n$ 士修。

CBE3B0A9373B197B35A607FE8E37CE2E.jpg

我們將一條水平向右走記為+1, 向上走記為-1, 那么就組成了一個(gè)n個(gè)+1和n個(gè)-1的序列, 我們所要保證的就是前k步中向右走的個(gè)數(shù)不小于向上走的次數(shù), 換句話說前k個(gè)元素的和非負(fù), 就是我們關(guān)于Catalan數(shù)的定義枷遂。

$\large 5.\ 多邊形劃分問題$
給定一個(gè)n邊形, 要求用n-3條不相交的對(duì)角線將其分為n-2個(gè)三角形, 求共有多少種分法。下圖是六邊形, 其總共有14種分法棋嘲。

FDF33BAB28A8D192BF888C2BE781842E.jpg

67ADFE28E379FA0580D9AB0A467E88E6.jpg

還記得我們?cè)诙嫠阉鳂淠遣糠痔岬降淖笥易訕溥f歸分割嗎, 此處也是相同的道理酒唉。假設(shè)n邊型共有n個(gè)頂點(diǎn), 依次將其編號(hào)為 $v_1,v_2\ldots, v_n$ 。從中任選一個(gè)頂點(diǎn) $v_k$ , 連接 $v_1$ 和 $v_k$ 沸移。

如上圖, 那么我們 $v_1v_k$ 這條線段將多邊形分成了兩部分, 一部分是從 $v_1$ 到 $v_k$ 共k個(gè)點(diǎn), 故為k邊形痪伦。而這個(gè)k邊形又可以當(dāng)做全新的多邊形, 遞歸地進(jìn)行下一次分割。

另一部分是從 $v_k到v_{n}$ 共n-k+1個(gè)點(diǎn)(因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=v_k" alt="v_k" mathimg="1">和 $v_n$ 點(diǎn)本身也包含在內(nèi)故要+1)雹锣。

那么此時(shí)我們就求得了遞推公式, 即:
$C_k\cdot C_{n-k+1}$
那么, 我們下一步就該求 $\sum$ 的上界了, $\sum$ 的上界就是在遞歸的一開始, 我們最多能選多少個(gè)點(diǎn)作為 $v_1$ 和 $v_k$ 的連線? 換句話說也就是求k的取值問題网沾。其實(shí) $v_k$ 的取值范圍是{ $v_2,v_3\ldots,v_{n-1}$ }共n-2個(gè)選擇。

為什么是到 $v_{n-1}$ 而不是到 $v_n$ 呢笆制？注意看上圖, $v_1$ 和 $v_k$ 是不是連在一起, 那也就是說我們沒法用 $v_1v_n$ 這條線斷將多邊形分為兩部分绅这。所以此時(shí)的通項(xiàng)公式可以寫為:

$C_n=\sum^{n-1}_2C_k\cdot C_{n-k+1}$

注意, n邊形的n要大于等于3。

寫為代碼為:

C[2]=C[3]=1;
for(int i=4;i<Max_n;i++)
{
C[i]=0;
for(int j=2;j<=i-1;j++)
C[i]+=C[j]*C[i-j+1];
}

那么我們此時(shí)就想, 能不能把這個(gè)通項(xiàng)公式簡(jiǎn)化一些呢?

既然討論所謂的“1邊型”在辆、“2邊型”其實(shí)根本沒有意義证薇，“3邊型”及以上才有意義度苔，而且3是n的起始值，那么不妨令 $C_n$ 表示n+2邊型的劃分?jǐn)?shù)浑度，這樣就從 $C_1=1$ 開始寇窑。換句話說, 我們此時(shí)需要改變一下設(shè)定n的方式, 之前是把n設(shè)定為n邊形邊的數(shù)量。現(xiàn)在加入給定的是六邊形, 我們就將n設(shè)定為6-2=4箩张。以此類推, n代表求的是n+2邊形, 此時(shí)我們既可以得到如下遞推公式:
$C_n=\sum^{n-1}_{0}C_iC_{n-1-i}$

$\large 6.\ 集合的不交叉劃分$
對(duì)于集合 $\{1,2,\ldots,2n\}$ 的不交叉劃分的數(shù)目為 $C_n$ 甩骏，這里解釋一下不交叉劃分。

我們對(duì)于集合{a,b}和{c,d}先慷，假設(shè)他們組成了兩個(gè)區(qū)間[a,b]和[c,d]饮笛，我們假設(shè)兩個(gè)區(qū)間不重合，那么以下四種情況當(dāng)做是不交叉的：a<c<d<b论熙，a<b<c<d福青，c<a<b<d與c<d<a<b，就是說兩個(gè)區(qū)間可以包含或者相離脓诡，那么此時(shí)我們稱集合{a,b}和{c,d}是不交叉的无午。

對(duì)于集合 $\{1,2,...,2n\}$ ，將里面元素兩兩分為一子集祝谚，共n個(gè)宪迟，若任意兩個(gè)子集都是不交叉的，那么我們稱此時(shí)的這個(gè)劃分為一個(gè)不交叉劃分交惯。此時(shí)不交叉的劃分?jǐn)?shù)就是我們的 $C_n$ 了次泽，證明也很容易，我們將每個(gè)子集中較小的數(shù)用左括號(hào)代替商玫，較大的用右括號(hào)代替箕憾，那么帶入原來的1至2n的序列中就形成了合法括號(hào)問題，就是我們第二點(diǎn)的結(jié)論拳昌。例如我們的集合{1,2,3,4,5,6}的不交叉劃分有五個(gè)：{{1,2},{3,4},{5,6}}袭异，{{1,2},{3,6},{4,5}}，{{1,4},{2,3},{5,6}}炬藤，{{1,6},{2,3},{4,5}}和{{1,6},{2,5},{3,4}}御铃。

$\large 7.\ 階梯切割$
n層的階梯切割為n個(gè)矩形的切法數(shù)也是 $C_n$ , 如下圖所示(下圖為n=4的情況):

09A59D33FA4653611AC3133DBAAB4DD5.jpg

我們先繪制如下的一張圖片，即n為5的時(shí)候的階梯:

C9E39AAE6A18225FA2BF2E8B2C30A27C.jpg

這個(gè)證明是怎么進(jìn)行的呢沈矿？首先我們令n等于5, 即5層階梯, 我們注意到每個(gè)切割出來的矩形都必需包括一塊標(biāo)示為*的小正方形上真，那么我們此時(shí)將每個(gè)*與#標(biāo)示的兩角作為矩形, 將其取出, 作為一種情況, 那么取出矩形后的階梯就剩下兩個(gè)小階梯, 這兩個(gè)小階梯就是兩個(gè)更小的子問題了。我們可以聯(lián)想二叉搜索樹那部分, 每次選擇一個(gè)節(jié)點(diǎn), 將序列分成左右兩半, 此處是每次選擇一個(gè)以*和#作為對(duì)角的矩形, 將整個(gè)階梯分為兩半羹膳。

那么具體的分法看下圖, 每種不同顏色的框代表是一種取出矩形的方法, 注意觀察取出框內(nèi)元素時(shí), 階梯內(nèi)剩余的元素被分為了兩個(gè)小階梯睡互。

075CC308460A2A5841DAE2090FAA06CE.jpg

因此我們有
$C_5 = C_0 * C_4 + C_1 * C_3 + C_2 * C_2 + C_1 * C_3 + C_0 * C_4$
很顯然這就是一個(gè)卡特蘭數(shù)。故其滿足通項(xiàng)公式
$\mathrm { C } _ { 0 } = 1 \quad , \quad C _ { n + 1 } = \frac { 2 ( 2 n + 1 ) } { n + 2 } C _ { n }$

$\large 8.\ 填數(shù)/排隊(duì)/照相問題$
假如有2n個(gè)人, 其身高都各不相同, 要求現(xiàn)在將這2n個(gè)人排成兩排, 要求: (1)每人比左邊的人高, 比右邊的人矮 (2)在同一列中的兩個(gè)人, 后面的比前面的高。

這道題咋看上去毫無(wú)頭緒, 但是抽象一下, 就是: 在一個(gè)2行n列的格子中填入1到2n這些數(shù)值使得每個(gè)格子內(nèi)的數(shù)值都比其右邊和下邊的所有數(shù)值都小的情況數(shù)就珠。

假設(shè)我們有8個(gè)數(shù), 即 1 2 3 4 5 6 7 8, 即此時(shí)n=4, 然后我們令這8個(gè)數(shù)從小到大排列, 現(xiàn)在我們從中隨機(jī)選4個(gè)數(shù), 放到第一行中, 剩下4個(gè)數(shù)放到第二行中, 假設(shè)我們的排列順序是:

1 2 3 4
5 6 7 8

其中1 2 3 4四個(gè)數(shù)在第一行, 5 6 7 8四個(gè)數(shù)在第二行, 假設(shè)在第一行設(shè)為0, 在第二行設(shè)為1, 那么這8個(gè)數(shù)所在隊(duì)列就可以表示為

1 2 3 4 5 6 7 8
0 0 0 0 1 1 1 1

如果我們的排列順序是:

1 2 5 7
3 4 6 8

其中1 2 5 7四個(gè)數(shù)在第一行, 3 4 6 8四個(gè)數(shù)在第二行, 那么這8個(gè)數(shù)就可以表示為:

1 2 3 4 5 6 7 8
0 0 1 1 0 1 0 1

看出規(guī)律來了嗎, 這其實(shí)就是卡特蘭數(shù)的變體, 假設(shè)我們現(xiàn)在有一個(gè) 不符合規(guī)則的排隊(duì)順序:

1 2 5 3
4 6 7 8

那么對(duì)應(yīng)的0和1序列就是:

1 2 3 4 5 6 7 8
0 0 0 1 0 1 1 1

你會(huì)發(fā)現(xiàn), 不對(duì)啊, 這雖然5比3大違背了規(guī)則, 但是從01序列上來看, 其符合卡特蘭數(shù)的條件啊, 是不是錯(cuò)了, 其實(shí)沒錯(cuò), 因?yàn)槲覀兇颂幹豢紤]組合, 而不是排列, 因?yàn)槟銜?huì)發(fā)現(xiàn), 下面這個(gè)排隊(duì)順序與上面那個(gè)不符合規(guī)則的排隊(duì)順序, 生成的01序列是一樣的, 都是00010111:

1 2 3 5
4 6 7 8

也就是說, 對(duì)于一種01序列, 很顯然只有一種排隊(duì)方式是正確的, 是一一映射的關(guān)系, 譬如:

1 2 3 5 | 1 3 2 5 | 1 2 5 3 | 3 1 2 5 | 3 5 2 1 | 5 3 1 2 ...
4 6 7 8 | 4 7 6 8 | 4 6 8 7 | 7 4 6 8 | 7 8 6 4 | 8 7 4 6 ...

上述所有排隊(duì)方式, 都對(duì)應(yīng)著00010111, 但是其中只有一種是正確的, 也就是排隊(duì)方式跟01序列是一一對(duì)應(yīng)的映射關(guān)系, 那么也就是說, 我們可以完全不考慮排隊(duì)方式, 只考慮總共有多少種可行的01序列即可, 因?yàn)橐环N01序列對(duì)應(yīng)且只對(duì)應(yīng)著一種排隊(duì)方式

而我們實(shí)踐后發(fā)現(xiàn), 可行的01序列就是卡特蘭數(shù)的要求, 可以類比于出棧入棧問題, 即 $C_n$ , 至此, 完全轉(zhuǎn)化為卡特蘭數(shù)問題

部分參考http://daybreakcx.is-programmer.com/posts/17315.html, https://www.cnblogs.com/wuyuegb2312/p/3016878.html#bop和https://www.cnblogs.com/13224ACMer/p/4671551.html
在寫這篇文章中, 瀏覽了很多博客, 如果有哪篇博客被引用我卻忘了指出, 懇請(qǐng)告知, 我即刻修改寇壳。

最后編輯于：2019.07.10 21:44:52

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市妻怎，隨后出現(xiàn)的幾起案子壳炎，更是在濱河造成了極大的恐慌，老刑警劉巖逼侦，帶你破解...
沈念sama閱讀 216,372評(píng)論 6贊 498
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件匿辩，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡榛丢，警方通過查閱死者的電腦和手機(jī)铲球，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,368評(píng)論 3贊 392
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來涕滋，“玉大人睬辐，你說我怎么就攤上這事挠阁”龇危” “怎么了？”我有些...
開封第一講書人閱讀 162,415評(píng)論 0贊 353
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵侵俗，是天一觀的道長(zhǎng)锨用。經(jīng)常有香客問我，道長(zhǎng)隘谣，這世上最難降的妖魔是什么增拥？我笑而不...
開封第一講書人閱讀 58,157評(píng)論 1贊 292
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮寻歧，結(jié)果婚禮上掌栅，老公的妹妹穿的比我還像新娘。我一直安慰自己码泛，他們只是感情好猾封，可當(dāng)我...
茶點(diǎn)故事閱讀 67,171評(píng)論 6贊 388
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著噪珊，像睡著了一般晌缘。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上痢站，一...
開封第一講書人閱讀 51,125評(píng)論 1贊 297
城市分裂傳說
那天磷箕，我揣著相機(jī)與錄音，去河邊找鬼阵难。笑死岳枷，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播空繁，決...
沈念sama閱讀 40,028評(píng)論 3贊 417
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼氢烘，長(zhǎng)吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來了家厌？” 一聲冷哼從身側(cè)響起播玖，我...
開封第一講書人閱讀 38,887評(píng)論 0贊 274
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎饭于，沒想到半個(gè)月后蜀踏，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 45,310評(píng)論 1贊 310
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡掰吕，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,533評(píng)論 2贊 332
?白月光啟示錄
正文我和宋清朗相戀三年果覆，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片殖熟。...
茶點(diǎn)故事閱讀 39,690評(píng)論 1贊 348
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡局待，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出菱属，到底是詐尸還是另有隱情钳榨，我是刑警寧澤，帶...
沈念sama閱讀 35,411評(píng)論 5贊 343
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布纽门，位于F島的核電站薛耻，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏赏陵。R本人自食惡果不足惜饼齿，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,004評(píng)論 3贊 325
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望蝙搔。院中可真熱鬧缕溉，春花似錦、人聲如沸吃型。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,659評(píng)論 0贊 22
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)败玉。三九已至敌土，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間运翼，已是汗流浹背返干。一陣腳步聲響...
開封第一講書人閱讀 32,812評(píng)論 1贊 268
情欲美人皮
我被黑心中介騙來泰國(guó)打工，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留血淌，地道東北人矩欠。一個(gè)月前我還...
沈念sama閱讀 47,693評(píng)論 2贊 368
代替公主和親
正文我出身青樓财剖，卻偏偏與公主長(zhǎng)得像，于是被迫代替她去往敵國(guó)和親癌淮。傳聞我的和親對(duì)象是個(gè)殘疾皇子躺坟，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,577評(píng)論 2贊 353

算法題面試題①-排列組合問題(母函數(shù)和卡特蘭數(shù))

母函數(shù)

普通母函數(shù)

卡特蘭數(shù)

推薦閱讀更多精彩內(nèi)容