Programarea dinamică poate fi blestemul existenței celor mai mulți ingineri software. Nu cred că există vreun subiect despre care să fi primit mai multe întrebări.
Și înțeleg perfect.
Intervievatorii adoră să pună aceste întrebări pentru că sunt dificile.
Intervievații se luptă cu adevărat pentru că nu au un cadru de rezolvare a problemelor pentru abordarea problemelor de programare dinamică.
Aceasta înseamnă că de fiecare dată când încercați să rezolvați o problemă de programare dinamică, începeți de la zero. Nu puteți aplica modelele pe care le-ați văzut cu alte probleme de PD, deoarece acestea arată total diferit. Așa că o luați mereu de la capăt și încercați să rezolvați aceste probleme dificile de la zero.
În această postare, vreau să vă arăt o modalitate mai bună.
VIDEO-urile următoare vă vor conduce prin 6 dintre cele mai comune probleme de PD pe care vă puteți aștepta să le vedeți în interviurile dumneavoastră. Dacă învățați aceste probleme și învățați cum să aplicați metoda FAST, veți fi într-o formă foarte bună pentru a aborda programarea dinamică în interviurile dumneavoastră.
Subtitrare: Dacă sunteți încă nou în programarea dinamică, consultați mai întâi ebook-ul nostru gratuit de 42 de pagini, Programare dinamică pentru interviuri
Veziți problemele:
Cel mai mic mărunțiș
Dată o cantitate de mărunțiș de intrare x, scrieți o funcție pentru a determina numărul minim de monede necesare pentru a face acea cantitate de mărunțiș.
eg. (folosind monede americane)
|
1
2
3
4
|
. change(1) = 1
change(3) = 3
change(7) = 3
change(32) = 4
|
Longest Common Substring
Date două șiruri de caractere, scrieți o funcție care să returneze cea mai lungă subșir comună.
eg.
longestSubstring("ABAB", "BABA") = "ABA"
Numărul Fibonacci
Dat un număr întreg n, scrieți o funcție care să calculeze al n-lea număr Fibonacci.
eg.
fibonacci(1) = 1fibonacci(5) = 5fibonacci(10) = 55
Submatrice pătrată
Dată o matrice 2D de 1s și 0s, găsiți cea mai mare subretea pătrată a tuturor 1s.
eg.
|
1
2
3
|
subarray(
) = 2
|
Produs matricial
Dată o matrice, găsiți calea din stânga sus în dreapta jos cu cel mai mare produs, deplasându-vă doar în jos și în dreapta.
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 Rucsac
Dată o listă de elemente cu valori și greutăți, precum și o pondere maximă, găsiți valoarea maximă pe care o puteți genera din elementele în care suma ponderilor este mai mică decât cea maximă.
eg.
|
1
2
3
|
items = {(w:1, v:6), (w:2, v:10), (w:3, v:12)}
maxWeight = 5
knapsack(items, maxWeight) = 22
|