Grundsätzlich habe ich ein Problem, das so ähnlich ist:
Es gibt einen Garten mit Erdbeerpflanzen, der durch eine quadratische 2D-Anordnung dargestellt wird. Jede Pflanze (jedes Element) hat eine Anzahl von Erdbeeren. Sie beginnen in der oberen linken Ecke des Arrays, und Sie können nur nach rechts oder nach unten bewegen. Ich muss eine rekursive Methode entwerfen, um die Wege durch den Garten zu berechnen und dann auszugeben, welche die meisten Erdbeeren ergibt.
Ich glaube, ich verstehe wirklich sehr einfache Rekursionsprobleme, aber dieses Problem ist mir über den Kopf gegangen. Ich bin mir nicht sicher, wo ich anfangen oder wohin ich gehen soll, wenn ich eine rekursive Methode erstelle.
Jede Hilfe, die sich auf den Code bezieht oder mir hilft, das Konzept hinter diesem Problem zu verstehen, wird sehr geschätzt. Danke.
Wie dasblinkenlight sagte, ist der effizienteste Weg, dies zu tun, eine Memoization oder dynamische Programmiertechnik. Ich bevorzuge dynamische Programmierung, aber hier verwende ich reine Rekursion.
Die Antwort dreht sich um die Antwort auf eine grundlegende Frage: "Wenn ich auf dem Feld in Zeile r und Spalte c auf meinem Feld bin, wie kann ich den Weg von oben links nach hier so bemessen, dass die Anzahl der Erdbeeren ist maximiert? "
Der Schlüssel zur Erkenntnis ist, dass es nur zwei Möglichkeiten gibt, um in die Handlung in Zeile r und Spalte c zu gelangen: entweder kann ich von oben kommen, indem ich die Handlung in Zeile r-1 und Spalte c verwende, oder ich kann dorthin gelangen von der Seite, unter Verwendung des Diagramms in Zeile r und Spalte c-1. Danach müssen Sie nur noch sicherstellen, dass Sie Ihre Basisfälle kennen ... was im Grunde bedeutet, dass meine rein rekursive Version etwa so aussehen würde:
%Vor%Rufen Sie max (r-1, c-1) an, um Ihre Antwort zu erhalten. Beachten Sie, dass es hier eine Menge Ineffizienz gibt; Sie werden viel besser mit dynamischer Programmierung (die ich unten bereitstellen werde) oder Memo (die bereits definiert wurde). Die Sache, an die man sich erinnern sollte, ist, dass sowohl die DP- als auch die Memoisierungstechniken einfach effizientere Wege sind, die von den hier verwendeten rekursiven Prinzipien herrühren.
DP:
%Vor%In beiden Fällen, wenn Sie den tatsächlichen Pfad wiederherstellen möchten, behalten Sie einfach eine 2D-Tabelle mit booleschen Werten bei, die "ob ich von oben oder nach links komme" entspricht. Wenn der meiste Erdbeerweg von oben kommt, wahr, sonst falsch gestellt. Dadurch können Sie den Patch nach der Berechnung zurückverfolgen.
Beachten Sie, dass dies im Prinzip immer noch rekursiv ist: Bei jedem Schritt schauen wir auf unsere vorherigen Ergebnisse zurück. Wir speichern zufällig unsere vorherigen Ergebnisse, so dass wir keinen Haufen Arbeit verschwenden, und wir greifen die Teilprobleme in einer intelligenten Reihenfolge an, so dass wir sie immer lösen können. Weitere Informationen zur dynamischen Programmierung finden Sie unter Wikipedia .
Sie können dies mit Memo tun. Hier ist eine Java-ähnliche Pseudodode ( memo , R und C werden als Instanzvariablen für die Methode max angenommen).
Das können Sie mit der DP-Tabelliermethode lösen, mit der Sie Platz von O (m * n) bis O (n) sparen können. Bei der DP-Speicherung benötigen Sie eine m * n-Matrix, um Zwischenwerte zu speichern. Folgendes ist mein Python-Code. Hoffe es kann helfen.
%Vor%