Dynamisch programmeren is misschien wel het schrikbeeld van het bestaan van de meeste software-ingenieurs. Ik denk niet dat er een onderwerp is waarover ik meer vragen heb gekregen.
En ik snap het helemaal.
Interviewers stellen deze vragen graag omdat ze moeilijk zijn.
Interviewers worstelen echt omdat ze geen raamwerk hebben voor het benaderen van DP-problemen.
Dat betekent dat je elke keer dat je een dynamisch programmeerprobleem probeert op te lossen, weer van voren af aan begint. Je kunt geen patronen toepassen die je bij andere DP-problemen hebt gezien, omdat die er totaal anders uitzien. Dus je begint altijd opnieuw en probeert deze moeilijke problemen vanaf nul op te lossen.
In deze post wil ik je een betere manier laten zien.
De volgende video’s lopen je door 6 van de meest voorkomende DP-problemen die je kunt verwachten te zien in je interviews. Als je deze problemen leert kennen en leert hoe je de FAST-methode toepast, ben je in zeer goede vorm om dynamisch programmeren in je interviews aan te pakken.
Protip: als dynamisch programmeren voor u nog onbekend is, bekijk dan eerst ons gratis ebook van 42 pagina’s, Dynamic Programming for Interviews
Bekijk de problemen:
Kleinste wisselgeld
Gegeven een ingevoerd bedrag aan wisselgeld x, schrijf een functie om het minimumaantal munten te bepalen dat nodig is om dat bedrag aan wisselgeld te maken.
eg. (bij gebruik van Amerikaanse munten)
|
1
2
3
4
|
change(1) = 1
change(3) = 3
change(7) = 3
change(32) = 4
|
Longest Common Substring
Gegeven twee strings, schrijf een functie die de langste gemeenschappelijke substring teruggeeft.
eg.
longestSubstring("ABAB", "BABA") = "ABA"
Fibonacci-getal
Geef een geheel getal n, schrijf een functie om het n-de Fibonacci-getal te berekenen.
eg.
fibonacci(1) = 1fibonacci(5) = 5fibonacci(10) = 55
Square Submatrix
Geef een 2D matrix van 1s en 0s, vind de grootste vierkante submatrix van alle 1s.
eg.
|
1
2
3
|
subarray(
) = 2
|
Matrix Product
Geef een matrix, zoek het pad van linksboven naar rechtsonder met het grootste product door alleen naar beneden en rechts te bewegen.
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 Knapzak
Gegeven een lijst van items met waarden en gewichten, en een max gewicht, zoek de maximale waarde die je kunt genereren uit items waarbij de som van de gewichten kleiner is dan de max.
eg.
|
1
2
3
|
items = {(w:1, v:6), (w:2, v:10), (w:3, v:12)}
maxWeight = 5
knapsack(items, maxWeight) = 22
|