алгоритм биномиального коэффициента с использованием динамического программирования и одномерного массива

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

Двухмерные массивы могут быть легко представлены в виде одномерных массивов.

вместо определения C[n+1][k+1], определите C2[(n+1)*(k+1)]. Затем вместо вызова C[a][b] звоните C2[b*(n+1)+a].

Answer 2

Ваш метод динамического программирования (с использованием 2D-массива) для решения биномиального коэффициента, кажется правильным. Обратите внимание, что нам не нужно хранить всю таблицу, только предыдущую строку. Таким образом, возможна реализация 1D!

Ниже приведен код для его реализации с использованием массива 1D.

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