Berechnung Binomialkoeffizienten mit dynamischer Programmierung

Question

Ich schrieb diesen Code Binomialkoeffizienten _n C _k zu finden:

# include <bits/stdc++.h> 
using namespace std; 
int c[20][20]; 
void initialize() 
{ 
    for(int i=0;i<20;i++) 
     for(int j=i;j<20;j++) 
      c[i][j]=-1; 
} 
int binomCoeff(int n,int k) 
{ 
    if(k==0||k==n) return 1; 
    if(c[n][k]!=-1) 
     return c[n][k]; 
    return c[n][k] = binomCoeff(n-1,k-1) + binomCoeff(n-1,k); 
} 

int main() 
{ 
    initialize(); 
    cout<<binomCoeff(4,2)<<endl; 
} 

Ich bin neu in der dynamischen Programmierung, so dass ich den Fehler nicht finden.

Answer 1

Sie verwenden den zweiten Index für k (kleine oder gleich n), sondern nur größere Indizes

for(int j= 0 ;j<20;j++) 
or 
for(int j= 0 ; j <= i ;j++) 

Hinweis initialisieren, dass dieser Fehler bei dem Schritt-für-Schritt-Debugging entdeckt werden würde. Warum haben Sie diesen Ansatz ignoriert?

P.S. Methode hier ist memoization - "top-down" Art der dynamischen Programmierung. Sie können auch "bottom-up" dynamische Programmierung als Übung implementieren - Tabelle in Reihenfolge füllen und das letzte Zellenergebnis erhalten.