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

在C语言中，使用动态规划解决组合数计算（即C(n, m)，也称为“n choose m”）的问题，通常涉及创建一个二维数组来存储中间结果，避免重复计算。这里是一个简单的斐波那契数列式的动态规划算法：

#include <stdio.h>

int choose(int n, int m) {
    // 初始化一个大小为(n+1)x(m+1)的数组，因为n和m的最大值不会超过n
    int dp[m + 1][n + 1];

    // 初始化边界条件
    for (int i = 0; i <= n; i++) {
        dp[i][0] = dp[0][i] = 1;
    }

    // 动态填充数组
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= min(i, m); j++) {
            dp[j][i] = dp[j - 1][i - 1] + dp[j][i - 1];
        }
    }

    return dp[m][n];
}

int main() {
    int n, m;
    printf("Enter the values of n and m: ");
    scanf("%d %d", &n, &m);
    if (m > n) {
        printf("Error: m should not be greater than n.\n");
        return 1;
    } else {
        int result = choose(n, m);
        printf("C(%d, %d) = %d\n", n, m, result);
    }
    return 0;
}

在这个程序中，`dp[j][i]`表示从n个元素中选择j个的不同组合数。通过递推公式 `dp[j][i] = dp[j - 1][i - 1] + dp[j][i - 1]`，我们可以计算出每一个组合的数量。