Module: 組み合わせ


Problem

1 /3


組み合わせ数

Theory Click to read/hide

n 個の要素の k による組み合わせは、n 個の要素から形成できる複合物であり、各接続で k 個の要素が集まります。一方、接続は要素自体によってのみ互いに​​異なります (配置順序の違いは考慮されません)。
 
たとえば、次の組み合わせは、3 つの要素 (a,b,c)(a,b,c) 2 つから形成できます: ab,ac,bc。
 
n 要素から k によって形成できるすべての可能な組み合わせの数は、記号  次の式で計算されます:
 
組み合わせの数を確認するには 2 つの方法があります 
 
1. n!、k!、(n – k)! を見つけてください。上記の式に従って、数量を計算しますが、オーバーフローの可能性があるため、このメソッドは n <= 12 で使用できます。
 
2.動的プログラミングを使用します。
 
DP はパスカルの三角形のように見え、上部と端に 1 があり、各数値はその上の 2 つの数値の合計に等しくなります。





O(n ^2 ) の動的計画法を使用して組み合わせの数をカウントする関数:

int C(int n, int k)
{
ベクトル<ベクトル<int> > dp(n + 1, ベクトルint>(n + 1, 1)); // サイズ (n + 1, n + 1) の dp 配列を作成します
for (int i = 0; i <= n; i++) // 配列の i 行目を埋めます
{
for (int j = 1; j < i; j++)
{
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; //(i - 1; j - 1) と (i - 1; j) を通じて (i;j) の位置を再計算します 
}
}
return dp[n][k]; //戻り値 
}

Problem

与えられた数値 nk (\(0 <= k <= n\),  ; \(0) 組み合わせの数を計算します  \(C_n^k\) < /span>。
 

 

<頭> <本体>
# 入力 出力
1 2 8 28