java - 使用动态规划和一维数组的二项式系数算法

Question

我知道一种动态编程算法来计算二维数组的二项式系数，如下所示。有没有办法利用一维数组？

int binomialCoeff(int n, int k)
{
int C[n+1][k+1];
int i, j;


for (i = 0; i <= n; i++)
 {
   for (j = 0; j <= min(i, k); j++)
    {

        if (j == 0 || j == i)
            C[i][j] = 1;


        else
            C[i][j] = C[i-1][j-1] + C[i-1][j];
    }
    }

  return C[n][k];
  }

Answer 1

您的动态规划方法(使用二维数组)来解决二项式系数，似乎是正确的。请注意，我们不需要保留整个表，只需保留前一行。因此一维实现是可能的!

下面是使用一维数组实现它的代码。

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