Dynamisches Programmieren/Fibonacci

[Noiz]

Hallo Zusammen. Ich habe eine Frage zu einem Beispiel bzgl. der Top-Down Programmierung.
Der rekursive Ansatz ist bekannt:

//rekursiv
int fib(int n){

if (n<1) return 0;

if (n==1) return 1;

return fib(n-1) + fib(n-2);

}

Hierzu meine Frage: Was genau soll die fett markierte Zeile (if (fibs[n]!=0) return fibs[n];) in diesem Beispiel bewirken? Und muss man das Array nicht innerhalb der Methode deklarieren? Wenn ich das Array innerhalb der Methode erstelle und die besagte Zeile weglasse, komme ich ebenfalls zum Ergebnis.


//Top-Down

int[] fibs = new int[n+1]

int fib(int n){

if (fibs[n]!=0) return fibs[n];

if (n==1) fibs[1] = 1;

if (n>1) fibs[n] = fib(n-1)+fib(n-2);

return fibs[n];

}

Vielen Dank vorab

 

[mihe7]

Was genau soll die fett markierte Zeile (if (fibs[n]!=0) return fibs[n];) in diesem Beispiel bewirken?

Sie sorgt dafür, dass die fibs[n] nur einmal berechnet werden.