Rekursion Funktion in eine Iterativ Funktion umwandeln

[AClassyWarius]

Hallo, ich komme gerade an einer Klausur Aufgabe überhaupt nicht weiter, ich soll eine rekursive Funktion in eine Iterative Funktion durch dynamisches Programmieren umschreiben.
a für b = 0
f(a,b) = b für a = 0
f(a - 1, b) + f(a, b-1) für a > 0 , b > 0

wäre echt genial wenn mir jemand einen kleinen Denkanstoß geben könnte, hab schon mehrere Wege versucht aber klappt einfach nicht.

public int getF(int a, int b) {
        if (b == 0) {
            return a;
        } else if (a == 0) {
            return b;
        } else if (a > 0 & b > 0) {
            return getF(a - 1, b) + getF(a, b - 1);
        }
        return -1;
    }

 

[JCODA]

Naja bei dynamischer Programmierung verwendet man ja meinst ein Array, um Teilergebnisse abzuspeichern. Dann benötigt man noch ein Verfahren, um das Array zu befüllen, aber dies ergibt sich meist einfach aus der Funktionsvorschrift, indem man sich anschaut, von welcher "Seite" man das Array ausrechnen kann. Zeichne dir hierfür am besten eine kleine Skizze für a=b=5 oder so.

 

[AClassyWarius]

ich hab mir schon aufrufsbäume aufgezeichnet, leider hat es mir nicht viel gebracht.

 

[JCODA]

Ich habe es mal implementiert, so sieht das Gerüst aus:

public static int getFIter(int a, int b) {
        int mem[][] = new int[a + 1][b + 1];
        //TODO fill mem
        return mem[a][b];
    }

Welche Stellen von mem kann man sofort ausfüllen?
Welche kann man danach füllen?

 

[AClassyWarius]

naja wenn a = 0, dann ist mem, wenn b = 0 ist mem[a][a] wenn a >0 , b > 0 dann ist mem[a-1] + mem[a][b-1] ? ^^

aber danke für den Ansatz

 

[AClassyWarius]

public static int getFIterativ(int a, int b) {
        int [][] memory = new int [a + 1][b + 1];
        memory[0][1] = 1;
        memory[1][0] = 1;
        for(int i = 1; i <= a; i++) {
            for(int j = 1; j <= b; j++) {
                memory[i][j] = memory[i-1][j] + memory[i][j-1];
            }
        }
        return memory [a][b];
    }

aber etwas passt noch nicht ganz

 

[AClassyWarius]

public static int getFIterativ(int a, int b) {
        int [][] memory = new int [a + 1][b + 1];
        memory[a][0] = a;
        memory[0][b] = b;
        for(int i = 1; i <= a; i++) {
            for(int j = 1; j <= b; j++) {
                memory[i][j] = memory[i-1][j] + memory[i][j-1];
            }
        }
        return memory [a][b];
    }

also für getF(1,3) = 7 aber ich bekomme nur 4 raus, leider finde ich den Fehler nicht -.-

 

[JCODA]

public class DynProg {

    public static void main(String[] args) {
        for (int a = 0; a < 10; a++) {
            for (int b = 0; b < 10; b++) {
                System.out.println("f(" + a + "," + b + ") = " + getFRec(a, b) + " : " + getFIter(a, b));
            }
        }
    }

    public static int getFIter(int a, int b) {
        int mem[][] = new int[a + 1][b + 1];
        /*for (int i = 0; i <= a; i++) {
            mem[i][0] = i;
        }
        for (int i = 0; i <= b; i++) {
            mem[0][i] = i;
        }*/
        for (int aa = 0; aa <= a; aa++) {
            for (int bb = 0; bb <= b; bb++) {
                if(aa == 0){
                    mem[aa][bb] = bb;
                }else if(bb==0){
                    mem[aa][bb] = aa;
                }else{
                    mem[aa][bb] = mem[aa - 1][bb] + mem[aa][bb - 1];
                }
            }
        }
        return mem[a][b];
    }

    public static int getFRec(int a, int b) {
        if (b == 0) {
            return a;
        } else if (a == 0) {
            return b;
        } else if (a > 0 & b > 0) {
            return getFRec(a - 1, b) + getFRec(a, b - 1);
        }
        return -1;
    }
}

Zunächst dachte ich, das einkommentierte wird benötigt, dann ist mir aufgefallen, wenn die Schleife mit 0 beginnt, klappt alles trotzdem. Das sieht jetzt sehr kompakt und "einfach" aus, aber bedenke, dass es nur funktioniert, weil ein "zeilenweises" Auffüllen von unten nach oben speziell -hier- funktioniert. Das mag bei anderen Problemen komplizierter sein.

 

[AClassyWarius]

tausend dank, durch deine Hilfe hab ich es endlich verstanden da kann die Klausur morgen ja kommen

 

[Blizzsnake80]

Hatte gerade ein ähnliches Problem zu lösen.
@JCODA: Vielen Dank für die super Erklärung !!!!!