Die dynamische Programmierung ist vielleicht der Fluch der Existenz der meisten Software-Ingenieure. Ich glaube nicht, dass es ein Thema gibt, zu dem ich mehr Fragen erhalten habe.
Und ich verstehe es vollkommen.
Interviewer lieben es, diese Fragen zu stellen, weil sie schwierig sind.
Interviewer haben es wirklich schwer, weil sie keinen Problemlösungsrahmen haben, um an DV-Probleme heranzugehen.
Das bedeutet, dass Sie jedes Mal, wenn Sie versuchen, ein dynamisches Programmierproblem zu lösen, bei Null anfangen. Man kann keine Muster anwenden, die man bei anderen DV-Problemen gesehen hat, weil sie völlig anders aussehen. Sie fangen also immer wieder von vorne an und versuchen, diese schwierigen Probleme von Grund auf zu lösen.
In diesem Beitrag möchte ich Ihnen einen besseren Weg zeigen.
Die folgenden Videos führen Sie durch 6 der häufigsten DV-Probleme, die Sie in Ihren Interviews erwarten können. Wenn du diese Probleme kennst und lernst, wie du die FAST-Methode anwendest, bist du in einer sehr guten Verfassung, um die dynamische Programmierung in deinen Vorstellungsgesprächen zu meistern.
Tipp: Wenn Sie noch neu in der dynamischen Programmierung sind, lesen Sie zuerst unser kostenloses 42-seitiges ebook, Dynamic Programming for Interviews
Schauen Sie sich die Probleme an:
Smallest Change
Schreiben Sie eine Funktion, um die minimale Anzahl von Münzen zu bestimmen, die erforderlich ist, um diesen Betrag an Wechselgeld zu erhalten.
eg. (mit amerikanischen Münzen)
|
1
2
3
4
|
change(1) = 1
change(3) = 3
change(7) = 3
change(32) = 4
|
Longest Common Substring
Gegeben zwei Strings, Schreiben Sie eine Funktion, die die längste gemeinsame Teilzeichenkette zurückgibt.
eg.
longestSubstring("ABAB", "BABA") = "ABA"
Fibonacci-Zahl
Schreibe eine Funktion zur Berechnung der n-ten Fibonacci-Zahl.
z.B..
fibonacci(1) = 1fibonacci(5) = 5fibonacci(10) = 55
Quadratische Untermatrix
Geben Sie eine 2D-Anordnung von 1en und 0en, finden Sie die größte quadratische Unteranordnung aller 1en.
eg.
|
1
2
3
|
subarray(
) = 2
|
Matrixprodukt
Gegeben eine Matrix, Finde den Weg von links oben nach rechts unten mit dem größten Produkt, indem du dich nur nach unten und rechts bewegst.
eg.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
1 -> 4 -> 7 -> 8 -> 9
2016
-1 -> 4 -> 5 -> -6 -> 9
1080
|
0-1 Knapsack
Gegeben eine Liste von Gegenständen mit Werten und Gewichten, sowie einer maximalen Gewichtung, finden Sie den maximalen Wert, den Sie aus Elementen erzeugen können, bei denen die Summe der Gewichte kleiner als die maximale Gewichtung ist.
eg.
|
1
2
3
|
items = {(w:1, v:6), (w:2, v:10), (w:3, v:12)}
maxGewicht = 5
knapsack(items, maxGewicht) = 22
|