c - 如何设置数组 B[0..n][0..k]。请帮助

Question

我必须使用动态编程实现代码来查找二项式系数。但我不知道如何设置数组 B。这里是我的代码:

#include <stdio.h>

int minimum(int a, int b) { return (a < b) ? a : b; }

main() {
    int n = 50, k;
    printf("Enter value for k:");
    scanf("%d", &k);
    printf("Value of coefficient %d, %d is: %d\n", n, k, bin2(n, k));

    return 0;
}

// code to be implemented

int bin2(int n, int k) {
    int i, j;

    // array to initialize. Help
    int B[0..n][0..k];

    for (i = 0; i <= n; i++)
        for (j = 0; j <= minimum(i, k); j++)
            if (j == 0 || j == i)
                B[i][j] = 1;
            else
                B[i][j] = B[i - 1][j - 1] + B[i - 1][j];
    return B[n][k];
}

Answer 1

您可以使用malloc()和calloc()功能来自 <stdlib.h>动态分配内存。由于您希望能够存储从 0 到 n 和 0 到 k 的索引，因此您必须创建一个 (n+1) × (k+1) 数组。这是通过分配 n+1 int* 的数组来完成的。指针，然后分配一个 k+1 int 的数组每个指针的值:

    /* Initialize array */
    B = malloc((n+1) * sizeof(int*));
    for (i=0; i<=n; i++) B[i] = calloc((k+1), sizeof(int));

当你的函数退出时，该内存仍然会被分配，但你将无法再访问它，因为 B 的值是本地的 bin2()功能并将永远丢失。 (这称为 memory leak 。)

所以你需要在返回之前释放这些内存:

    int result = B[n][k];

    /* Dispose of array */
    for (i=0; i<=n; i++) free(B[i]);
    free(B);

    return result;
}

(顺便说一下，你问的不是 dynamic programming ，而是 dynamic memory allocation 。还有 better ways of calculating binomial coefficients 。)