d134 - 00369 - Combinations
題目描述
題目要求計算從 N 個物品中取出 M 個物品的組合數，即 C(N, M)。輸入為 N 和 M，輸出格式為 "N things taken M at a time is C exactly."，其中 C 為組合數。輸入 N=0, M=0 時結束程式。
解題思路
此題使用動態規劃 (Dynamic Programming) 計算組合數。組合數 C(N, M) 可以使用 Pascal's Triangle 的性質來計算，即 C(N, M) = C(N-1, M-1) + C(N-1, M)。程式碼預先計算了 C(i, j) 的值，並儲存在 DP 陣列中，然後根據輸入的 N 和 M 直接輸出 DP[N][M] 的值。DP 陣列的初始化處理了邊界條件，例如 C(i, 0) = 1 和 C(i, i) = 1。
複雜度分析
- 時間複雜度: O(N^2)
- 空間複雜度: O(N^2)
程式碼
#include <iostream>
using namespace std;
unsigned long long int DP[101][101];
int main(){
for(int i=0;i<101;++i){
DP[i][0]=1;
DP[i][i]=1;
DP[i][1]=i;
DP[i][i-1]=i;
}
for(int i=2;i<101;++i)
for(int j=2;j<=i;++j)
if(!DP[i][j])
DP[i][j]=DP[i-1][j-1]+DP[i-1][j];
int n,m;
while(cin >> n >> m){
if(!n&&!m)break;
cout << n << " things taken " << m << " at a time is " << DP[n][m] << " exactly.\n";
}
}