遞推公式小結

閑來無事，把幾個遞推公式做了一下總結。

斐波那契

這個應該是大家比較熟悉的遞推公式了吧，比如問你有2行n列的長方形方格，要求用n個1*2的骨牌鋪滿。有多少種鋪法？，那麼這題我們可以想到可以通過n-1時以及n-2時轉移過來，于是答案即為斐波那契數列的第n項。

遞推公式： f[i]=f[i−1]+f[i−2]

組合數

對于求解n個數中選擇m個有多少種方案，我們可以想到使用組合數求解，而對于中等資料範圍，多次查詢的題目我們可以使用遞推組合數的方法求解，所得的即為楊輝三角表。

原公式： C(n,m)=n!m!(n−m)!

遞推公式： C[i][j]=C[i−1][j−1]+C[i−1][j]

錯排公式

十本不同的書放在書架上。現重新擺放，使每本書都不在原來放的位置。有幾種擺法？

這種問題即為錯排問題，設 D[i] 為有i個物品的方案數，于是我們考慮使用遞推法求解。

第一步，把第 n 個元素放在一個位置，比如位置k，一共有 n−1 種方法；

第二步，放編号為 k 的元素，這時有兩種情況：

⑴把它放到位置n，那麼，對于剩下的 n−1 個元素，由于第 k 個元素放到了位置n，剩下 n−2 個元素就有 D[n−2] 種方法；

⑵第 k 個元素不把它放到位置n，這時，對于這 n−1 個元素，有 D[n−1] 種方法；

最終，我們得到了一個公式： D[i]=(i−1)∗(D[i−1]+D[i−2]) 此即為錯排公式

卡特蘭數

矩陣連乘： P=A1×A2×A3×……×An ，依據乘法結合律，不改變其順序，隻用括号表示成對的乘積，試問有幾種括号化的方案？

合法的括号序列，排隊買票，凸包的劃分三角形問題都可以使用卡特蘭數解決，我們設合法的解決方案數為 h(n) ，于是我們能推出一個很暴的函數啊 h(n)=h(0)∗h(n−1)+h(1)∗h(n−2)+...+h(n−1)∗h(0) ，先别着急啊，這隻是最基本的公式，還有更暴的遞推式：

h(n)=h(n−1)∗(4∗n−2)

對于這個東西如何做到非遞推求解呢？

我們有兩個等價的式子

h(n)=C(2n,n)n+1

h(n)=C(2n,n)−C(2n,n−1)

于是我們可以借助之前提到的組合數得到問題的答案啦。