這個經典問題有兩種解法。
解法一：
設\(f(x)\)為\(x\)個數入棧後，再全部出棧的序列數量
假設我們有\(4\)個數\(a,b,c,d\), 我們來看\(a\)的出棧順序.
假如\(a\)第一個出棧，那麼後面還有\(3\)個數沒有出棧，因此方法數是\(f(3)\).
假設\(a\)第二個出棧，那麼\(a\)的前面有\(1\)個數已經出棧，後面還有\(2\)個數沒有出棧，因此方法數為\(f(1) * f(2)\).
假設\(a\)第三個出棧，那麼\(a\)的前面有\(2\)個數已經出棧，後面還有\(1\)個數沒有出棧，因此方法數為\(f(2) * f(1)\).
同理，\(a\)第四個出棧的方法數為\(f(3)\).
那麼我們就可以得到\(f(4) = f(3) + f(1) *f(2) + f(2)*f(1) +f(3)\).
對於\(n\)來推廣一下，可以得到：\(f(n)=\sum_{i=1}^{n}f(i - 1)*f(n-i)\).
不難發現這就是卡特蘭數，這裡就不在贅述了。
解法二：
我們假設\(-1\)表示出棧，\(1\)表示入棧，這樣我們就可以用\(-1\)和\(1\)組成的序列來表示出入棧操作。
首先來限定一些條件，一個合法的序列\(0\)和\(1\)的數量一定是相等的。並且序列的字首和一定是不小於\(0\)的。
瞭解了上面兩個條件後，我們知道所有的序列數為\(C^{\ n}_{2n}\),因為\(-1\)和\(1\)的數量相同。在這\(C^{\ n}_{2n}\)個序列中，存在不合法的序列，即字首和小於\(0\)的序列，我們想要知道這些不合法的序列有多少。
假設我們有一個序列\(1,-1,-1,1,-1,1\)，這裡在第三個下標，我們發現了它的字首和小於\(0\)，因此它不合法。再來推廣一下，在這所有\(C^{\ n}_{2n}\)個序列中，不合法的序列它的字首和一定在某一處小於\(0\).
接下來，我們將序列開頭到不合法下標的這一段進行取反。首先拿上面的例子來進行說明，取反後得到：\(-1,1,1,1,-1,1\)，不難發現，現在得到的序列\(+1\)比\(-1\)多出一個.
現在再來進行推廣，我們擷取的不合法序列段(從開頭到不合法字首和下標)，這一段中的\(-1\)一定比\(+1\)多一個，那麼將這一段取反後所得到的總序列中的\(+1\)一定比\(-1\)多一個。
不難發現，不合法的序列一定對應唯一一個取反後的序列，並且取反後的序列中\(+1\)有\(n+1\)個，\(-1\)有\(n-1\)個，那麼根據這個條件，我們就可以得到所有不合法的序列數量為\(C_{2n}^{n+1}\)或者\(C^{n-1}_{2n}\)(因為他兩相等)。
最後，合法的序列數為：\(C^{\ n}_{2n}-C_{2n}^{n+1\ or\ n-1}\).
這個解法的關鍵在於，不合法的序列一定唯一對應一個取反後的序列，那麼我們可以算出所有取反後的數列有多少種(根據\(+1\)有\(n+1\)個，\(-1\)有\(n-1\)個的性質)，來對應出不合法的序列數，從而得到答案.
因為感覺這種解法非常的巧妙，因此想寫篇部落格來總結一下.