Binomialkoeffizienten-Algorithmus mit dynamischer Programmierung und einem eindimensionalen Array - Java

Ich kenne einen dynamischen Programmieralgorithmus, um die Binomialkoeffizienten mit zweidimensionalem Array wie folgt zu berechnen. Gibt es eine Möglichkeit, ein eindimensionales Array zu verwenden?

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

Antworten:

Ihre dynamische Programmiermethode (unter Verwendung eines 2D-Arrays) zur Lösung des Binomialkoeffizienten scheint richtig zu sein. Beachten Sie, dass wir nicht die gesamte Tabelle behalten müssen, sondern nur die vorherige Zeile. So ist 1D-Implementierung möglich!

Nachfolgend finden Sie den Code zum Implementieren mit einem 1D-Array.

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

Zweidimensionale Arrays können leicht als eindimensionale Arrays dargestellt werden.

anstatt zu definieren C[n+1][k+1]einige definieren C2[(n+1)*(k+1)]. Dann statt zu rufen C[a][b] Anruf C2[b*(n+1)+a].