c语言用动态规划求组合数(C nm)的算法

在C语言中，可以使用动态规划的方法来计算组合数(C(n, m))。组合数表示从n个不同元素中取出m个元素的不同组合数目，其公式为C(n, m) = n! / (m!(n-m)!)，其中“!”表示阶乘。动态规划在此问题中的应用通常通过一个二维数组或称为“lookup table”存储中间结果，避免了重复计算。

下面是一个简单的动态规划算法步骤：

1. 定义一个大小为(n+1)x(m+1)的数组dp，初始化所有元素为0，dp[i][j]表示从i个元素中取j个元素的组合数。

2. 初始化两个边界条件：
- dp[0][0] = 1; 表示从0个元素中取0个元素有1种方式，即空集。
- 对于1 <= i <= n 和 j == 0 或者 j == i，dp[i][j] = 1; 分别表示从i个元素中取0个或全部元素有1种方式。

3. 动态填充数组：
- 使用循环遍历dp数组，对于每个(i, j)，如果0 < j < i，则dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; 根据组合数公式，从i个元素中取j个元素等于从(i-1)个元素中取j-1个元素和取j个元素之和。

4. 组合数的值就在dp[n][m]中。

下面是伪代码形式：

int combination(int n, int m) {
    int dp[m + 1];
    for (int i = 0; i <= n; ++i) {
        dp[0] = 1;
        for (int j = 1; j <= min(i, m); ++j) {
            dp[j] = dp[j - 1] * (i - j + 1) / j; // 计算组合数
        }
    }
    return dp[m];
}