Java-Programmierung: Dynamische Programmierung am Treppenbeispiel

Question

Ein Mann läuft eine Treppe mit n Stufen hoch und kann entweder 1 Stufe, 2 Stufen oder 3 Stufen auf einmal gehen. Schreiben Sie nun ein Programm, um zu zählen, wie viele mögliche Wege das Kind die Treppe hochlaufen kann.

Der gegebene Code sieht wie folgt aus

public static int countDP(int n, int[] map) {
 if (n<0)
   return 0;
 else if (n==0)
   return 1;
 else if (map[n]>-1)
   return map[n];
 else {
    map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map);
    return map[n]; }
 }

Ich kenne C und C++, nicht JAVA. Dies stammt aus dem Buch "Cracking the Coding interview". Könnte mir jemand erklären

1. warum und wie sie die Funktion map hier verwendet? Ist map hier ein Array?

2. Ich sehe keine Zeile zum Speichern einer Eingabe im map-Array, aber wie würde es dennoch etwas zurückgeben?

3. Hat jemand eine Idee, wie der C++ oder C-Version dieses Codes aussehen könnte? Es ist schwer, diesen Code zu verstehen. Vielleicht nicht wegen der JAVA-Grammatik, sondern wegen der impliziten Struktur des dynamischen Programmierens.

4. Was wäre die Zeitkomplexität dieses Algorithmus? Sollte sie kleiner als O(3^n) sein?

Ich würde es sehr schätzen.

Vielen Dank, Leute

Answer 1

Okay, hier ist, was der Code macht.

`if (n<0)`
    `return 0;`

Wenn nicht genug Schritte übrig sind, dann zähle es nicht. Zum Beispiel, wenn noch zwei Schritte übrig sind, aber der Benutzer versucht drei Schritte zu machen, dann wird dies nicht als mögliche Kombination gezählt.

else if (n==0)   return 1;

Wenn die Anzahl der verbleibenden Schritte der Anzahl der verfügbaren Schritte entspricht, die der Benutzer machen möchte, ist dies eine mögliche Kombination. Also, gib eine 1 zurück, weil dies eine mögliche Kombination ist und zur Gesamtanzahl der gültigen Kombinationen hinzugefügt werden sollte.

else if (map[n]>-1)   return map[n];

Hier kommt der Teil des dynamischen Programmierens. Nehmen wir an, dass alle Werte im Array den Wert -1 hatten. Also, wenn die Zahl größer als -1 ist, wurde sie bereits gelöst, also gib die Gesamtanzahl der Kombinationen aus Schrittnummer n zurück, anstatt sie neu zu lösen.

`map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map);`

return map[n]; }

Schließlich löst dieser Teil den Code. Die Anzahl der möglichen Kombinationen entspricht der Anzahl der möglichen Kombinationen, die der Benutzer erhalten kann, wenn er 1 Schritt macht, plus der Anzahl der möglichen Kombinationen, die der Benutzer erhalten kann, wenn er 2 Schritte macht, plus der Anzahl der möglichen Kombinationen, die der Benutzer erhalten kann, wenn er drei Schritte macht.

Ein Beispiel, nehmen wir an, es gibt 5 Schritte

Ein einfacher Durchlauf könnte so aussehen:

//Die Anzahl der Lösungen vom fünften Schritt

countDp(5) = countDp(4)+countDp(3)+countDp(2);

//Anzahl der Lösungen vom vierten Schritt

countDP(4) = countDp(3)+countDp(2)+countDp(1);

//Anzahl der Lösungen vom dritten Schritt

countDp(3) = countDp(2)+countDp(1)+countDp(0);
//Anzahl der Lösungen vom zweiten Schritt
countDp(2) = countDp(1)+countDp(0)+countDp(-1);
//Anzahl der Lösungen vom ersten Schritt
countDp(1) = countDp(0) + countDp(-1)+countDp(-2);
//Schließlich der Basisfall
countDp(0) = 1;

countDp(-1)= 0;
countDp(-2)= 0;
countDp(1) = 1+0+0 = 1;
countDp(2) = 1+1+0 = 2;  //Dynamische Programmierung: musste countDp(1) nicht neu berechnen, sondern schaute den Wert in map[1] nach
countDp(3) = 2+1+1 = 4;  //Dynamische Programmierung, musste nicht countDp(1), countDp(2) neu lösen, sondern schaute den Wert in map[1] und map[2] nach
countDp(4) = 4+2+1=7 //Dynamische Programmierung, musste nicht CountDp(3),CountDp(2), CountDp(1) neu lösen, sondern schaute sie in map[3], map[2], map[1] nach
countDp(5)=  2+4+7=13 //Dynamische Programmierung, benutzte einfach map[4]+map[3]+map[2]

Answer 2

Warum und wie benutzt sie die Funktion map hier?

Das Buch zeigt eine dynamische Programmierungstechnik namens memoization. Sie wird verwendet, um zu vermeiden, dass dieselbe Zahl erneut berechnet wird: Wenn das Element nicht -1 ist, wurde es bereits berechnet, und eine erneute Berechnung würde bedeuten, dass viele CPU-Zyklen verschwendet werden. DP berechnet den Wert einmal und gibt ihn dann jedes Mal zurück, wenn der Wert benötigt wird.

map hier ist ein Array, oder?

Richtig, map ist von Typ Array.

Ich sehe keine Zeile, um eine Eingabe im map-Array zu speichern, aber wie würde es etwas zurückgeben?

Das wäre die Zuweisung in der dritten Zeile von unten:

map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map);

Hat jemand eine Idee für eine C++ oder C-Version dieses Codes? Es ist schwer, diesen Code zu verstehen. Vielleicht nicht wegen der JAVA-Grammatik, sondern wegen der impliziten Struktur der dynamischen Programmierung.

Richtig, DP und Memoization benötigen etwas Zeit, um sich daran zu gewöhnen. Lassen Sie den Algorithmus einmal mit Papier und Bleistift für eine kleine Zahl, sagen wir 10, durchlaufen. Dies wird Ihnen zeigen, wie die optimale Teilstruktur der Antwort diesem Algorithmus hilft, so schnell eine Antwort zu finden.

Was wäre die Zeitkomplexität dieses Algorithmus? Sollte sie kleiner als O(3^n) sein?

Absolut! Jedes Element wird genau einmal berechnet, und jedes Element benötigt amortisiert O(1) zum Berechnen, daher beträgt die Gesamtkomplexität dieses Codes O(N). Dies mag gegensätzlich sein, wenn Sie beobachten, wie die Kette rekursiver Aufrufe zur Berechnung von countDP(K) eine O(K) rekursive Aufrufe benötigt. Jeder Aufruf beendet jedoch die Berechnung von K Elementen des Arrays map (beachten Sie, wie map eine Einbahnstraße ist: Sobald Sie einen nicht-negativen Wert in eine Zelle setzen, bleibt dieser für immer nicht-negativ, sodass eine erneute Berechnung desselben Werts über einen anderen Aufrufpfad die gleiche Zeit O(1) benötigen würde.

Answer 3

1.) map ist ein Integer-Array. Die Notation in Java besagt, dass map[n] den Integer-Wert am Index n zurückgibt.

2.) Das Ergebnis ist ein Integer, weil map[n] den Integer-Wert am Index n zurückgibt. Der einzige Zeitpunkt, zu dem ein Wert im Array gespeichert wird, ist bei

map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map);

Dies ist ein rekursiver Aufruf, um die Summe der Schritte zu finden, indem alle möglichen Kombinationen von 1, 2 und 3 gezählt werden.

3.)

int countDP(int n, int map[])
{
if (n<0)
    return 0;
else if (n==0)
    return 1;
else if (map[n]>-1)
    return map[n];
else {
    map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map);
    return map[n]; 
}

}

4.) Ja, die Komplexität wäre viel schneller als O(3^n).

Answer 4

JavaScript-Lösung: (iterativ)

function countPossibleWaysIterative(n) {
  if (n < 0){
    return -1; // Überprüfen auf negative Zahl, eventuell auch auf Integer prüfen
  } if (n === 0) {
    return 0; // für den Fall mit 0 Treppenstufen
  } else if (n === 1) {
    return 1; // für den Fall mit 1 Treppenstufe
  } else if (n === 2) {
    return 2; // für den Fall mit 2 Treppenstufen
  } else {

    var prev_prev = 1;
    var prev = 2;
    var res = 4; // für den Fall mit 3 Treppenstufen

    while (n > 3) { // für alle anderen Fälle
      var tmp = prev_prev + prev + res;
      prev_prev = prev;
      prev = res;
      res = tmp;
      n--;
    }
  }
  return res;
}

Answer 5

/**
 * Erstellt von mona am 3/3/16.
 */
import java.util.Hashtable;
public class StairCount {
    /*
     Ein Mann läuft eine Treppe mit n Stufen hinauf und kann entweder 1 Stufe, 2 Stufen
     oder 3 Stufen auf einmal gehen. Zähle, wie viele mögliche Wege das Kind die Treppe hochlaufen kann.
     */
    static Hashtable ht=new Hashtable<>();

    public static long stairs(int n){
        if (!ht.containsKey(1)){
            ht.put(1, (long) 1);
        }
        if (!ht.containsKey(2)){
            ht.put(2, (long) 2);
        }
        if (!ht.containsKey(3)){
            ht.put(3, (long) 4);
        }

/*
        if (!ht.containsKey(n)){
            ht.put(n, stairs(n-1)+ht.get(1)+stairs(n-2)+ht.get(2)+stairs(n-3)+ht.get(3));
        }
*/
        if (!ht.containsKey(n)){
            ht.put(n, stairs(n-1)+stairs(n-2)+stairs(n-3));
        }
        return ht.get(n);
    }
    public static void main(String[] args){
        System.out.println(stairs(4));

    }
}

//die Antwort für 4 ist 14 und für 5 ist 27. Für die kommentierte Zeile. Kann jemand kommentieren, warum mein Denkprozess falsch war?