使用一维数组设计二项式系数算法

Question

我已经设计了以下使用二维数组确定二项式系数的算法。例如，要计算 n 选择 k 的二项式系数，我们可以创建一个二维数组，如下所示：

int[][] arr = new int[n][k];

我们可以通过以下方式填充数组：

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

但是，我需要重新设计此算法以使用索引 0-k 的一维数组。我在确定如何执行此操作时遇到了很多麻烦。我从小步开始，发现了一些常见的情况：

如果k = 0，arr[0]将为1，无论n如何，都会返回。
如果k=1，arr[0]就是1，arr[1]应该是n，如果我是循环设计的话

当我说 k = 2 时，这就是它变得棘手的地方，因为 arr[2] 的值实际上取决于之前的值。我相信当我循环时（比如从 i = 0 到 i = n），arr[] 的值会改变，但我不太明白如何改变。我从这些方面着手：

for(int i = 0; i <= n; i++){
   for(int j = 0; j <= minimum(i, k); j++){
      if(j == 0 || i == j){
         arr[j] = 1;
      } else if(j == 1){
         arr[j] = i;
      } else{
         arr[j] = ??; // I can't access previous values, because I didn't record them?
      }
   }
}

我该如何处理？

Answer 1

这是一个只使用一个一维数组的代码：

int[] coefficients = new int[k + 1];
coefficients[0] = 1;
for (int i = 1; i <= n; i++) {
    for (int j = k; j >= 1; j--) {
        coefficients[j] += coefficients[j - 1];
    }
}

为什么是正确的？要计算固定 i 的 coefficients[j]，我们需要知道 i - 1 的 coefficients[j - 1] 和 coefficients[j] 的值。如果我们从 k 向下迭代到 0，我们可以安全地为当前位置记录一个新值，因为我们永远不需要它的旧值。

使用一维数组设计二项式系数算法

Design the binomial coefficient algorithm using a single dimensional array

arrays

algorithm

binomial-coefficients

pascals-triangle