组合


n个元素与k的组合是可以由n个元素形成的化合物，在每个连接中收集k个元素；而连接之间的区别仅在于元素本身（不考虑排列顺序的差异）。
 
例如，以下组合可以由 3 个元素 (a,b,c)(a,b,c) 各组成 2：ab,ac,bc。
 
用符号 计算公式：
<分区> 
求组合数的方法有两种 
 
<分区>1。找到 n!, k!, (n – k)!并根据上面的公式，我们计算数量，但是从 –由于可能溢出，此方法可与 n <= 12 一起使用。
 
<分区>2。用动态规划。
 
DP 看起来像帕斯卡三角形，顶部和边缘都有一个，每个数字等于它上面两个数字的总和。





在 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)位置
}
}
返回 dp[n][k]; //返回值
}

Training problem

组合数