La programmazione dinamica può essere la rovina dell’esistenza di molti ingegneri del software. Non credo che ci sia un argomento su cui ho ricevuto più domande.
E lo capisco perfettamente.
Gli intervistatori amano fare queste domande perché sono difficili.
Gli intervistati fanno davvero fatica perché non hanno una struttura di risoluzione dei problemi per affrontare i problemi di DP.
Questo significa che ogni volta che si cerca di risolvere un problema di programmazione dinamica, si parte da zero. Non puoi applicare i modelli che hai visto con altri problemi DP perché sembrano totalmente diversi. Quindi si ricomincia sempre da capo e si cerca di risolvere questi difficili problemi da zero.
In questo post, voglio mostrarvi un modo migliore.
I seguenti video vi guideranno attraverso 6 dei più comuni problemi di DP che potete aspettarvi di vedere nelle vostre interviste. Se imparate questi problemi e imparate ad applicare il metodo FAST, sarete in ottima forma per affrontare la programmazione dinamica nei vostri colloqui.
Suggerimento: Se sei ancora alle prime armi con la programmazione dinamica, dai un’occhiata al nostro ebook gratuito di 42 pagine, Dynamic Programming for Interviews, prima
Guarda i problemi:
Smallest Change
Data in input una somma di denaro x, scrivi una funzione per determinare il numero minimo di monete necessarie per fare quella somma di denaro.
eg. (usando monete americane)
|
1
2
3
4
|
change(1) = 1
change(3) = 3
change(7) = 3
change(32) = 4
|
Longest Common Substring
Date due stringhe, scrivi una funzione che restituisca la sottostringa comune più lunga.
eg.
longestSubstring("ABAB", "BABA") = "ABA"
Numero di Fibonacci
Dato un numero intero n, scrivere una funzione che calcoli l’ennesimo numero di Fibonacci.
eg.
fibonacci(1) = 1fibonacci(5) = 5fibonacci(10) = 55
Sottomatrice quadrata
Data una matrice 2D di 1 e 0, trovare la più grande sottomatrice quadrata di tutti gli 1.
eg.
|
1
2
3
|
subarray(
) = 2
|
Prodotto della matrice
Data una matrice, trova il percorso dall’alto a sinistra al basso a destra con il prodotto maggiore muovendosi solo verso il basso e verso destra.
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
Data una lista di oggetti con valori e pesi, e un peso massimo, trova il valore massimo che puoi generare dagli elementi in cui la somma dei pesi è inferiore al massimo.
eg.
|
1
2
3
|
items = {(w:1, v:6), (w:2, v:10), (w:3, v:12)}
maxWeight = 5
knapsack(items, maxWeight) = 22
|