Dynamisk programmering kan vara de flesta programvaruingenjörers problem. Jag tror inte att det finns något ämne som jag har fått fler frågor om.
Och jag förstår det helt och hållet.
Intervjuare älskar att ställa dessa frågor eftersom de är svåra.
Intervjupersonerna kämpar verkligen för att de inte har ett ramverk för problemlösning för att närma sig DP-problemen.
Det innebär att varje gång du försöker lösa ett dynamiskt programmeringsproblem så börjar du från ruta ett. Du kan inte tillämpa mönster som du sett med andra DP-problem eftersom de ser helt annorlunda ut. Så du börjar alltid om och försöker lösa dessa svåra problem från början.
I det här inlägget vill jag visa dig ett bättre sätt.
De följande videorna kommer att gå igenom 6 av de vanligaste DP-problemen som du kan förvänta dig att se i dina intervjuer. Om du lär dig dessa problem och lär dig att tillämpa FAST-metoden kommer du att vara i mycket god form för att ta itu med dynamisk programmering i dina intervjuer.
Tips: Om du fortfarande är nybörjare på dynamisk programmering, kolla in vår kostnadsfria 42-sidiga e-bok, Dynamic Programming for Interviews, först
Kolla på problemen:
Småste förändring
Givet ett inmatat växelbelopp x, skriv en funktion som bestämmer det minsta antalet mynt som krävs för att få fram det växelbeloppet.
eg. (med amerikanska mynt)
|
1
2
3
4
|
. change(1) = 1
change(3) = 3
change(7) = 3
change(32) = 4
|
Längsta gemensamma understräng
Givet två strängar, Skriv en funktion som returnerar den längsta gemensamma delsträngen.
eg.
longestSubstring("ABAB", "BABA") = "ABA"
Fibonacci-tal
Givet ett heltal n, skriv en funktion som beräknar det n:e Fibonacci-talet.
eg.
fibonacci(1) = 1fibonacci(5) = 5fibonacci(10) = 55
Förmåttlig delmatris
Givet en 2D-matris av 1:or och 0:or, hitta den största kvadratiska delmatrisen av alla 1:or.
eg.
|
1
2
3
|
subarray(
) = 2
|
Matrixprodukt
Givet en matris, Hitta vägen från övre vänster till nedre höger med störst produkt genom att bara röra dig nedåt och åt höger.
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 lista med föremål med värden och vikter, samt en maxvikt, hitta det maximala värdet som du kan generera från objekt där summan av vikterna är mindre än maxvärdet.
eg.
|
1
2
3
|
items = {(w:1, v:6), (w:2, v:10), (w:3, v:12)}
maxWeight = 5
knapsack(items, maxWeight) = 22
|