La programación dinámica puede ser la perdición de la existencia de la mayoría de los ingenieros de software. No creo que haya ningún tema sobre el que haya recibido más preguntas.
Y lo entiendo perfectamente.
A los entrevistadores les encanta hacer estas preguntas porque son difíciles.
Los entrevistados realmente luchan porque no tienen un marco de resolución de problemas para abordar los problemas de DP.
Eso significa que cada vez que intentas resolver un problema de programación dinámica, estás empezando desde cero. No puedes aplicar los patrones que has visto con otros problemas de AD porque son totalmente diferentes. Así que siempre estás empezando de nuevo y tratando de resolver estos difíciles problemas desde cero.
En este post, quiero mostrarte una manera mejor.
Los siguientes videos te guiarán a través de 6 de los problemas de AD más comunes que puedes esperar ver en tus entrevistas. Si aprendes estos problemas y aprendes a aplicar el Método FAST, estarás en muy buena forma para abordar la programación dinámica en tus entrevistas.
Consejo: Si todavía eres nuevo en la programación dinámica, echa un vistazo a nuestro ebook gratuito de 42 páginas, Programación dinámica para entrevistas, primero
Mira los problemas:
El cambio más pequeño
Dada una cantidad de cambio de entrada x, escribe una función para determinar el número mínimo de monedas necesarias para hacer esa cantidad de cambio.
eg. (usando monedas americanas)
|
1
2
3
4
|
cambio(1) = 1
cambio(3) = 3
cambio(7) = 3
cambio(32) = 4
|
Subsecuencia común más larga
Dadas dos cadenas, escriba una función que devuelva la subcadena común más larga.
eg.
longestSubstring("ABAB", "BABA") = "ABA"
Número Fibonacci
Dado un número entero n, escriba una función que calcule el enésimo número Fibonacci.
Ej.
fibonacci(1) = 1fibonacci(5) = 5fibonacci(10) = 55
Submatriz cuadrada
Dada una matriz 2D de 1s y 0s, encuentre la mayor submatriz cuadrada de todos los 1s.
Ej.
|
1
2
3
|
subarray(
) = 2
|
Producto de matrices
Dada una matriz, encuentra el camino de arriba a la izquierda a abajo a la derecha con el mayor producto moviéndose sólo hacia abajo y hacia la derecha.
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
Dada una lista de elementos con valores y pesos, así como un peso máximo, encontrar el valor máximo que se puede generar a partir de los elementos en los que la suma de los pesos es menor que el máximo.
eg.
|
1
2
3
|
items = {(w:1, v:6), (w:2, v:10), (w:3, v:12)}
maxPeso = 5
knapsack(items, maxPeso) = 22
|