algoritmo del coefficiente binomiale che utilizza la programmazione dinamica e un array monodimensionale - java

Conosco un algoritmo di programmazione dinamica per calcolare i coefficienti binomiali con array bidimensionale come sotto: Esiste un modo per utilizzare un array monodimensionale?

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

risposte:

Il tuo metodo di programmazione dinamica (utilizzando array 2D) per risolvere il coefficiente binomiale sembra corretto. Si noti che non è necessario mantenere l'intera tabella, solo la riga precedente. Quindi l'implementazione 1D è possibile!

Di seguito è riportato il codice per implementarlo utilizzando un array 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];
}

Gli array bidimensionali possono essere facilmente rappresentati come array monodimensionali.

invece di definire C[n+1][k+1], definisci alcuni C2[(n+1)*(k+1)]. Quindi, invece di chiamare C[a][b] chiamata C2[b*(n+1)+a].