c453 - TOI2003 第二題：疊羅漢
題目描述
題目要求計算在 n 個人底層的情況下，可以形成多少種不同的疊羅漢組合。疊羅漢的規則是，只能在任意連續兩人的肩膀上支撐一個人，以此類推。
解題思路
這道題目實際上是求第 n 個卡塔蘭數。卡塔蘭數在組合數學中經常出現，可以應用於多種計數問題。在這個問題中，我們可以將疊羅漢的組合看作二元樹的結構，其中底層的 n 個人是葉子節點，而每一層疊上去的人可以看作二元樹的內部節點。
程式碼中，ans[i] 儲存的是第 i 個卡塔蘭數。程式使用迴圈計算卡塔蘭數，利用卡塔蘭數的遞迴公式：C(n+1) = (2*(2*n+1) / (n+2)) * C(n)。 程式先初始化 ans[0] 為 1，然後迭代計算 ans[1] 到 ans[20]。最後，程式讀取輸入的 n 值，並輸出 ans[n]。
複雜度分析
- 時間複雜度: O(n)
- 空間複雜度: O(n)
程式碼
#include <iostream>
using namespace std;
long long int ans[21]={1};
int n;
int main(){
for(int i=0;i<=20;++i)
ans[i+1]=(2*(2*i+1)*ans[i])/(i+2);
while(cin >> n)
cout << ans[n] << "\n";
}