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

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];
    }
}

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