Dynamické programování může být pro většinu softwarových inženýrů postrachem jejich existence. Myslím, že neexistuje téma, na které bych dostal více otázek.
A já to naprosto chápu.
Tazatelé se rádi ptají na tyto otázky, protože jsou těžké.
Tazatelé s nimi opravdu bojují, protože nemají rámec pro řešení problémů DP.
To znamená, že pokaždé, když se snažíte vyřešit problém dynamického programování, začínáte od začátku. Nemůžete použít vzory, které jste viděli u jiných problémů DP, protože vypadají úplně jinak. Takže vždy začínáte znovu a snažíte se tyto obtížné problémy vyřešit od nuly.
V tomto příspěvku vám chci ukázat lepší způsob.
Následující videa vás provedou 6 nejčastějšími problémy DP, které můžete očekávat při pohovorech. Pokud se tyto problémy naučíte a naučíte se používat metodu FAST, budete na tom s dynamickým programováním při pohovorech velmi dobře.
Tip: Pokud s dynamickým programováním teprve začínáte, přečtěte si nejprve naši bezplatnou 42stránkovou e-knihu Dynamické programování pro přijímací pohovory
Podívejte se na úlohy:
Nejmenší změna
Při zadané vstupní částce změny x napište funkci, která určí minimální počet mincí potřebných k provedení této částky změny.
např. (při použití amerických mincí)
|
1
2
3
4
|
. change(1) = 1
change(3) = 3
change(7) = 3
change(32) = 4
|
Nejdelší společný podřetězec
Při dvou řetězcích, napište funkci, která vrátí nejdelší společný podřetězec.
např.
longestSubstring("ABAB", "BABA") = "ABA"
Fibonacciho číslo
Dáno celé číslo n, napište funkci, která vypočítá n-té Fibonacciho číslo.
např.
fibonacci(1) = 1fibonacci(5) = 5fibonacci(10) = 55
Čtvercová podmřížka
Dáno 2D pole 1 a 0, najděte největší čtvercovou podmřížku všech 1.
např.
|
1
2
3
|
subarray(
) = 2
|
Matrix Product
Dáno maticí, najděte cestu z levého horního rohu do pravého dolního rohu s největším součinem pohybem pouze dolů a doprava.
např.
|
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 Batoh
Dán seznam položek s hodnotami a váhami, a také maximální váhu, najděte maximální hodnotu, kterou můžete vytvořit z položek, u nichž je součet vah menší než max.
např.
|
1
2
3
|
items = {(w:1, v:6), (w:2, v:10), (w:3, v:12)}
maxWeight = 5
knapsack(items, maxWeight) = 22
|