A dinamikus programozás lehet a legtöbb szoftverfejlesztő létezésének csapása. Nem hiszem, hogy van olyan téma, amelyről több kérdést kaptam volna.
És teljesen megértem.
Az interjúztatók szeretik feltenni ezeket a kérdéseket, mert nehezek.
Az interjúalanyok azért küzdenek igazán, mert nincs problémamegoldó keretrendszerük a DP problémák megközelítéséhez.
Ez azt jelenti, hogy minden alkalommal, amikor megpróbálsz megoldani egy dinamikus programozási problémát, a nulláról indulsz. Nem tudod alkalmazni a más DP-problémáknál látott mintákat, mert azok teljesen másképp néznek ki. Így mindig elölről kezded, és a nulláról próbálod megoldani ezeket a nehéz problémákat.
Ezzel a bejegyzéssel egy jobb módszert szeretnék mutatni neked.
A következő videókon végigvezetlek 6 leggyakoribb DP-problémán, amelyekkel várhatóan találkozhatsz az interjúkon. Ha megtanulod ezeket a problémákat, és megtanulod, hogyan alkalmazd a FAST módszert, akkor nagyon jó formában leszel, hogy megbirkózz a dinamikus programozással az interjúkon.
Tipp: Ha még új vagy a dinamikus programozásban, először nézd meg ingyenes 42 oldalas ebookunkat, a Dinamikus programozás interjúkhoz címűt
Nézd meg a problémákat:
A legkisebb változás
Adott egy bemeneti pénzösszeg x, írj egy függvényt, amely meghatározza az adott pénzösszeghez szükséges minimális érmeszámot.
Pl. (amerikai érmékkel)
|
1
2
3
4
|
. change(1) = 1
change(3) = 3
change(7) = 3
change(32) = 4
|
Longest Common Substring
Adott két string, Írj egy függvényt, amely visszaadja a leghosszabb közös részláncot.
eg.
longestSubstring("ABAB", "BABA") = "ABA"
Fibonacci-szám
Adva egy n egész számot, írjon függvényt, amely kiszámítja az n-edik Fibonacci-számot.
Pl.
fibonacci(1) = 1fibonacci(5) = 5fibonacci(10) = 55
Négyzetes almátrix
Adva egy 1-ekből és 0-kból álló 2D-s tömböt, keresse meg az összes 1-esből álló legnagyobb négyzetes almátrixot.
Pl.
|
1
2
3
|
subarray(
) = 2
|
Mátrixprodukt
Adott egy mátrix, Keressük meg azt az utat balról fentről jobbra lentre, ahol a legnagyobb a szorzat, ha csak lefelé és jobbra haladunk.
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
Adott egy lista a tételek értékeivel és súlyaival, valamint egy max súlyt, keressük meg a maximális értéket, amelyet olyan elemekből állíthatunk elő, amelyeknél a súlyok összege kisebb, mint a max érték.
eg.
|
1
2
3
|
items = {(w:1, v:6), (w:2, v:10), (w:3, v:12)}
maxWeight = 5
knapsack(items, maxWeight) = 22
|