1

我已经设计了以下算法，该算法使用二维数组确定二项式系数。例如，要计算 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?
      }
   }
}

我该如何处理？

4

1 回答 1

4

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

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值，我们需要知道 和coefficients[j - 1]的coefficients[j]值i - 1。如果我们从kdown 迭代到0，我们可以安全地为当前位置记录一个新值，因为我们永远不需要它的旧值。

于 2015-03-01T21:30:09.807 回答