Dynamisk programmering er nok de fleste softwareingeniørers svøbe. Jeg tror ikke, der er noget emne, som jeg har fået flere spørgsmål om.
Og jeg forstår det helt.
Interviewere elsker at stille disse spørgsmål, fordi de er svære.
Interviewere kæmper virkelig, fordi de ikke har en problemløsningsramme til at nærme sig DP-problemer.
Det betyder, at hver gang du prøver at løse et dynamisk programmeringsproblem, starter du fra nul. Du kan ikke anvende mønstre, du har set med andre DP-problemer, fordi de ser helt anderledes ud. Så du starter altid forfra og forsøger at løse disse vanskelige problemer fra bunden.
I dette indlæg vil jeg vise dig en bedre måde.
De følgende videoer vil føre dig gennem 6 af de mest almindelige DP-problemer, som du kan forvente at se i dine interviews. Hvis du lærer disse problemer og lærer at anvende FAST-metoden, vil du være i meget god form til at tackle dynamisk programmering i dine interviews.
Tip: Hvis du stadig er ny i dynamisk programmering, så tjek først vores gratis 42 siders e-bog, Dynamic Programming for Interviews, ud
Kig på problemerne:
Smindste ændring
Givet et inputbeløb x, skriv en funktion til at bestemme det mindste antal mønter, der kræves for at lave det pågældende beløb.
eg. (ved brug af amerikanske mønter)
|
1
2
3
4
|
change(1) = 1
change(3) = 3
change(7) = 3
change(32) = 4
|
Længste fælles understreng
Givet to strenge, skriv en funktion, der returnerer den længste fælles understreng.
eg.
longestSubstring("ABAB", "BABA") = "ABA"
Fibonacci-tal
Givet et heltal n, skriv en funktion, der beregner det niende Fibonacci-tal.
eg.
fibonacci(1) = 1fibonacci(5) = 5fibonacci(10) = 55
Firkantet undermatrix
Givet et 2D-array af 1’ere og 0’ere, find det største kvadratiske underarray af alle 1’ere.
eg.
|
1
2
3
|
subarray(
) = 2
|
Matrixprodukt
Givet en matrix, Find den vej fra øverst til venstre til nederst til højre med det største produkt ved kun at bevæge sig nedad og til højre.
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
Givet en liste af genstande med værdier og vægte, samt en maks. vægt, skal du finde den maksimale værdi, du kan generere fra elementer, hvor summen af vægtene er mindre end maks.
eg.
|
1
2
3
|
items = {(w:1, v:6), (w:2, v:10), (w:3, v:12)}
maxWeight = 5
knapsack(items, maxWeight) = 22
|