台中女中程式解題系統：b025: 棋盤格城市

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

題目連結 http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b025。

分析完題目後，會得到這是 combination 問題：
C(n, k) = C(n-1, k-1) + C(n-1, k)
C(n, 0) = C(n, n) = 1

程式碼：

1. #include <iostream>  
2.   
3. using namespace std;  
4.   
5. long long int combi(int n, int k)  
6. {  
7.     long long int C[n + 1][k + 1];  
8.     int i, j;  
9.   
10.     for (i = 0; i <= n; i++)  
11.     {  
12.         for (j = 0; j <= min(i, k); j++)  
13.         {  
14.             if (j == 0 || j == i) // C(n, 0) = C(n, n) = 1  
15.                 C[i][j] = 1;  
16.             else // C(n, k) = C(n-1, k-1) + C(n-1, k)  
17.                 C[i][j] = C[i - 1][j - 1] + C[i - 1][j];  
18.         }  
19.     }  
20.   
21.     return C[n][k];  
22. }  
23.   
24. int main()  
25. {  
26.     int x, y;  
27.     cin >> x >> y;  
28.     cout << combi(x+y, x) << endl;  
29.   
30.     return 0;  
31. }