组合数计算
进阶组合数是组合数学的基础，常用于概率和计数问题。
// 算法讲解
组合数计算
演示组合数 C(n,k) 的递推计算过程。
待机
速度 中
待机 ⌨1int comb(int n, int k) {
2 vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
3 for (int i = 0; i <= n; i++) dp[i][0] = 1;
4 for (int i = 1; i <= n; i++)
5 for (int j = 1; j <= min(i, k); j++)
6 dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
7 return dp[n][k];
8}
复杂度分析
时间 O(nk)
空间 O(nk)
最优 O(nk)
最坏 O(nk)
算法讲解
组合数 C(n,k) 表示从 n 个元素中选 k 个的方案数。
递推公式：C(n,k) = C(n-1,k-1) + C(n-1,k)，边界 C(n,0) = C(n,n) = 1。
时间复杂度 O(nk)，空间复杂度 O(nk)。
常用于概率计算、排列组合、DP 状态转移等场景。