如何将二项式系数DP的空间复杂度变为O(n)？

Question

这是动态规划算法。

int bin2(int n, int k){
        index i, j;
        i tn B[0 ][0 k] B[0..n][0..k]; i
            for(i=0; i <= n; i++)
                for(j=0; j <= minimum(i,k); j++)
                    if (j 0 || j i) [i][j] 1
                        i
                        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];
    }

它的空间复杂度是O(n^2)。这可以降低到 O(n) 吗？能用'when the calculation of a row is finished, the previously calculated value is not needed'的属性怎么办？在上面的代码中，我得到一个提示，您可以将 k 更改为 1，将 j 更改为 j%2。我该怎么办？

Answer 1

关键是这一行

B[i][j] = B[i-1][j-1] + B[i-1][j];

你看，对于当前状态，我们依赖于 i-1 和 j-1。我们不需要前面的所有行，只需要第 i-1 行。

方法一

您应该将其更改为类似

的内容

B[j] += B[j - 1];

继续覆盖相同的一维数组，即为每个 i.

迭代 j

尝试自己解决。如果你还想看解决方案，在我的回答末尾。

方法二

有些人喜欢保留两行，一排用于早期，一排用于当前。他们使用 mod 在第 0 行和第 1 行之间交替。当 i = 0 时 (i+1) % 2 会给出 1，当 i = 1 时会给出 0。但是这个方法使用了两个数组而不是方法一所示的一个数组。

方法三

类似于方法2，有些人保留两个数组previous和current。他们交换整个数组而不是更改当前要填充的数组。交换发生在 j 循环之后和 i 循环内部。此方法参考@Maurycyt 的解决方案。

效率方面：方法 1 > 方法 2 > 方法 3

方法 1 的解决方案：

int binomialCoeff(int n, int k) 
{ 
    vector<int> dp(k+1, 0);

    dp[0] = 1;
  
    for (int i = 1; i <= n; i++) 
    { 
        for (int j = min(i, k); j > 0; j--) 
            dp[j] += dp[j-1]; 
    } 
    return dp[k]; 
}

Answer 2

我对你的代码感到困惑，它似乎有几个拼写错误，但这里是你如何评估线性空间复杂度的 {n \choose k}，使用 {n \choose k} = (n !)/(k!*(n-k)!) 是 Pascal 三角形的 n-th 行的 k-th 元素（你似乎已经知道了，我只是确保它出来了在这里）。

int nchoosek(int n, int k)
{
  int i, j; //These are indices of the row and column respectively
  int oldrow [n+1], newrow [n+1]; //n+1 is the largest size of a row we will need.
  //we will be computing a row of Pascal's triangle based on the previous row,
  //then swapping the two.
  for (i = 0; i <= n; i++) //we iterate over the rows
  {
    for (j = 0; j <= i; j++) //we iterate over the elements in a row, there are i+1 elements in row i, thus n+1 elements in row n.
    {
      if (j == 0 || j == i)
        newrow[j] = 1; //we set the first and last element of a row to 1.
      else
        newrow[j] = oldrow[j-1] + oldrow[j]; //we set the other elements to the sum of the two elements above them in Pascal's triangle.
    }
    swap(oldrow, newrow); //we swap the two arrays, and will now be counting the next row, using the row which we just counted.
  }
  //the i-th row of Pascal's triangle will always end up in the oldrow array
  return oldrow[k]; //we return its k-th element.
}

如何将二项式系数DP的空间复杂度变为O(n)？

How to change the spatial complexity of DP of binomial coefficient to O(n)?

algorithm

dynamic-programming