Dynamische Programmierung: Beispiele, allgemeine Probleme und Lösungen

Es besteht kein Zweifel, dass dynamische Programmierprobleme in einem Coding-Interview sehr einschüchternd sein können. Selbst wenn Sie wissen, dass ein Problem mithilfe einer dynamischen Programmiermethode gelöst werden muss, ist es eine Herausforderung, in einem begrenzten Zeitraum eine funktionierende Lösung zu finden.

Der beste Weg, um bei dynamischen Programmierproblemen gut zu sein, besteht darin, so viele wie möglich durchzugehen. Sie müssen sich nicht unbedingt die Lösung für jedes Problem merken, aber es ist gut, eine Vorstellung davon zu haben, wie Sie eines implementieren können.

Was ist dynamische Programmierung?

Einfach ausgedrückt ist die dynamische Programmierung eine Optimierungsmethode für rekursive Algorithmen, von denen die meisten zur Lösung von Rechen- oder mathematischen Problemen verwendet werden.

Sie können es auch als algorithmische Technik zur Lösung eines Optimierungsproblems bezeichnen, indem Sie es in einfachere Unterprobleme aufteilen. Ein Schlüsselprinzip, auf dem die dynamische Programmierung basiert, ist, dass die optimale Lösung eines Problems von den Lösungen seiner Unterprobleme abhängt.

Überall dort, wo wir eine rekursive Lösung sehen, bei der dieselben Eingaben wiederholt aufgerufen werden, können wir sie mithilfe dynamischer Programmierung optimieren. Die Idee ist, die Ergebnisse von Teilproblemen einfach zu speichern, damit wir sie nicht später neu berechnen müssen, wenn sie später benötigt werden.

Dynamisch programmierte Lösungen weisen eine Polynomkomplexität auf, die eine viel schnellere Laufzeit als andere Techniken wie Rekursion oder Backtracking gewährleistet. In den meisten Fällen reduziert die dynamische Programmierung die Zeitkomplexität, auch bekannt als Big-Ovon exponentiell zu polynomisch.

Was ist Big-O-Notation?

Ihr Code muss effizient sein, aber wie zeigen Sie, wie effizient etwas ist? Mit Big-O!

Nachdem Sie eine gute Vorstellung davon haben, was dynamische Programmierung ist, ist es an der Zeit, einige häufig auftretende Probleme und deren Lösungen zu untersuchen.

Dynamische Programmierprobleme

1. Rucksackproblem

Problemstellung

Bestimmen Sie anhand einer Reihe von Elementen mit jeweils einem Gewicht und einem Wert die Anzahl der Elemente, die in a enthalten sein sollen Sammlung, damit das Gesamtgewicht einen bestimmten Grenzwert nicht überschreitet und der Gesamtwert so groß ist wie möglich.

Sie erhalten zwei ganzzahlige Arrays Werte [0..n-1] und Gewichte [0..n-1] die Werte und Gewichte darstellen, die jeweils n Elementen zugeordnet sind. Ebenfalls angegeben ist eine Ganzzahl W. welches die Rucksackkapazität darstellt.

Hier lösen wir das 0/1-Rucksackproblem. Dies bedeutet, dass wir entweder einen Artikel hinzufügen oder ihn ausschließen können.

Algorithmus

• Erstellen Sie ein zweidimensionales Array mit n + 1 Zeilen und w + 1 Säulen. Eine Zeilennummer n bezeichnet die Menge von Elementen von 1 bis ichund eine Spaltennummer w bezeichnet die maximale Tragfähigkeit der Tasche.
• Der numerische Wert bei [i] [j] bezeichnet den Gesamtwert der Artikel bis ich in einer Tasche, die ein maximales Gewicht von j tragen kann.
• An jeder Koordinate [i] [j] Wählen Sie im Array den Maximalwert aus, den wir ohne erhalten können Punkt ioder der Maximalwert, mit dem wir erhalten können Punkt ije nachdem, welcher Wert größer ist.
• Der maximal erreichbare Wert durch Einbeziehung von Artikel i ist die Summe der Artikel ich selbst und der Maximalwert, der mit der verbleibenden Kapazität des Rucksacks erhalten werden kann.
• Führen Sie diesen Schritt aus, bis Sie den Maximalwert für das gefunden haben W.^th Reihe.

Code

def FindMax (W, n, Werte, Gewichte):
MaxVals = [[0 für x im Bereich (W + 1)] für x im Bereich (n + 1)]
für i im Bereich (n + 1):
für w im Bereich (W + 1):
wenn i == 0 oder w == 0:
MaxVals [i] [w] = 0
elif Gewichte [i-1] <= w:
MaxVals [i] [w] = max (Werte [i-1]
+ MaxVals [i-1] [w-Gewichte [i-1]], 
MaxVals [i-1] [w])
sonst:
MaxVals [i] [w] = MaxVals [i-1] [w]
MaxVals zurückgeben [n] [W]

2. Münzwechselproblem

Problemstellung

Angenommen, Sie erhalten eine Reihe von Zahlen, die die Werte jeder Münze darstellen. Finden Sie bei einem bestimmten Betrag die Mindestanzahl an Münzen, die für diesen Betrag erforderlich sind.

Algorithmus

• Initialisieren Sie ein Array mit einer Größe n + 1, wobei n der Betrag ist. Initialisieren Sie den Wert jedes Index ich im Array gleich der Menge sein. Dies gibt die maximale Anzahl von Münzen (unter Verwendung von Münzen mit dem Nennwert 1) an, die erforderlich sind, um diesen Betrag zu bilden.
• Da es für 0 keinen Nennwert gibt, initialisieren Sie den Basisfall wo Array [0] = 0.
• Für jeden anderen Index ichvergleichen wir den Wert darin (der anfänglich auf gesetzt ist n + 1) mit dem Wert Array [i-k] +1, wo k ist weniger als ich. Dies überprüft im Wesentlichen das gesamte Array bis i-1, um die minimal mögliche Anzahl von Münzen zu finden, die wir verwenden können.
• Wenn der Wert bei einem Array [i-k] + 1 ist kleiner als der vorhandene Wert bei Array [i], ersetzen Sie den Wert bei Array [i] mit dem bei Array [i-k] +1.

Code

def coin_change (d, betrag, k):
Zahlen = [0] * (Betrag + 1)
für j im Bereich (1, Betrag + 1):
Minimum = Menge
für i im Bereich (1, k + 1):
if (j> = d [i]):
Minimum = min (Minimum 1 + Zahlen [j-d [i]])
Zahlen [j] = Minimum
Rückgabewerte [Betrag]

3. Fibonacci

Problemstellung

Die Fibonacci-Reihe ist eine Folge von ganzen Zahlen, wobei die nächste ganze Zahl in der Reihe die Summe der beiden vorherigen ist.

Es wird durch die folgende rekursive Beziehung definiert: F (0) = 0, F (n) = F (n-1) + F (n-2), wo F (n) ist das n^th Begriff. In diesem Problem müssen wir alle Zahlen in einer Fibonacci-Sequenz bis zu einem gegebenen n erzeugen^th Begriff.

Algorithmus

• Verwenden Sie zunächst einen rekursiven Ansatz, um die angegebene Wiederholungsrelation zu implementieren.
• Die rekursive Lösung dieses Problems führt zum Zusammenbruch F (n) in F (n-1) + F (n-2)und dann die Funktion mit aufrufen F (n-1) und F (n + 2) als Parameter. Wir machen das bis zu den Basisfällen wo n = 0, oder n = 1 erreicht sind.
• Jetzt verwenden wir eine Technik namens Memoization. Speichern Sie die Ergebnisse aller Funktionsaufrufe in einem Array. Dies stellt sicher, dass für jedes n, F (n) muss nur einmal berechnet werden.
• Für alle nachfolgenden Berechnungen kann sein Wert einfach in konstanter Zeit aus dem Array abgerufen werden.

Code

def Fibonacci (n): 
fibNums = [0, 1] 
für i im Bereich (2, n + 1):
fibNums.append (fibNums [i-1] + fibNums [i-2])
return fibNums [n] 

4. Längste zunehmende Folge

Problemstellung

Ermitteln Sie die Länge der am längsten ansteigenden Teilsequenz innerhalb eines bestimmten Arrays. Die am längsten zunehmende Teilfolge ist eine Teilfolge innerhalb eines Arrays von Zahlen mit aufsteigender Reihenfolge. Die Zahlen innerhalb der Teilsequenz müssen eindeutig und in aufsteigender Reihenfolge sein.

Außerdem müssen die Elemente der Sequenz nicht aufeinanderfolgend sein.

Algorithmus

• Beginnen Sie mit einem rekursiven Ansatz, bei dem Sie den Wert der am längsten ansteigenden Teilsequenz von berechnen jedes mögliche Subarray von Index Null bis Index i, wobei i kleiner oder gleich der Größe von ist Array.
• Um diese Methode in eine dynamische umzuwandeln, erstellen Sie ein Array, in dem der Wert für jede Teilsequenz gespeichert wird. Initialisieren Sie alle Werte dieses Arrays auf 0.
• Jeder Index ich dieses Arrays entspricht der Länge der am längsten ansteigenden Teilsequenz für ein Subarray der Größe ich.
• Nun zu jedem rekursiven Aufruf von findLIS (arr, n), Überprüf den n^th Index des Arrays. Wenn dieser Wert 0 ist, berechnen Sie den Wert mit der Methode im ersten Schritt und speichern Sie ihn im n^th Index.
• Geben Sie schließlich den Maximalwert aus dem Array zurück. Dies ist die Länge der am längsten ansteigenden Teilsequenz einer bestimmten Größe n.

Code

def findLIS (myArray):
n = len (myArray)
lis = [0] * n
für i im Bereich (1, n):
für j im Bereich (0, i):
wenn myArray [i]> myArray [j] und lis [i] lis [i] = lis [j] +1
maxVal = 0
für i im Bereich (n):
maxVal = max (maxVal, lis [i])
Rückgabe maxVal

Lösungen für dynamische Programmierprobleme

Nachdem Sie einige der beliebtesten Probleme bei der dynamischen Programmierung durchlaufen haben, ist es an der Zeit, die Lösungen selbst zu implementieren. Wenn Sie nicht weiterkommen, können Sie jederzeit auf den Algorithmus-Abschnitt für jedes der oben genannten Probleme zurückgreifen.

Angesichts der heutigen Beliebtheit von Techniken wie Rekursion und dynamischer Programmierung schadet es nicht, einige beliebte Plattformen zu besuchen, auf denen Sie solche Konzepte erlernen können Verbessern Sie Ihre Codierungsfähigkeiten. Während Sie möglicherweise nicht täglich auf diese Probleme stoßen, werden Sie sie sicherlich in einem technischen Interview antreffen.

Das Know-how für häufig auftretende Probleme zahlt sich natürlich aus, wenn Sie sich für Ihr nächstes Interview entscheiden. Also mach dein auf Lieblings-IDEund los geht's!

Die 9 besten Code-Along-YouTube-Kanäle zum Erlernen der Programmierung

Bereit, mit dem Codieren zu beginnen? Diese YouTube-Kanäle sind eine großartige Möglichkeit, um mit Spielen, Apps, dem Web und anderen Entwicklungen zu beginnen.

Über den Autor