Hmmm … esto va a ser largo.
Primero tratemos de entender qué es DP.
La programación dinámica es una técnica matemática para resolver problemas.
En términos simples, significa Recursión (o iteración, para el caso, depende de si sigues un enfoque ascendente o descendente) junto con Memoization .
- Cómo encontrar el salto más pequeño
- ¿Qué tan difícil es el algoritmo de verificación de traducción de Duolingo? ¿Existen otras herramientas de código abierto similares por ahí?
- Ahora que los bitcoins son famosos y caros, ¿cómo reaccionaría el mercado ante un clon de Bitcoin que utiliza un algoritmo, tecnología, etc. idénticos?
- ¿Por qué no puedo resolver mi Cubo de Rubik de 4 x 4 x 4 como un cubo de Rubik de 3 x 3 x 3 si ya he hecho los centros y los bordes?
- ¿TFIDF es una métrica para medir qué tan informativa es una palabra o un algoritmo de aprendizaje automático?
Ahora entendamos la memorización. Sí, suena como una palabra elegante, pero en términos crudos significa anotar cosas, es decir, almacenar lo que ha calculado una vez y almacenarlo en una nota (diccionario) para su posterior reutilización para evitar cálculos repetidos, por lo tanto, disminuir el cálculo efectivo hora.
Ahora, como somos claros con los términos básicos, tomemos algunos ejemplos para defender la causa de la DP.
Problema: escriba un programa para dar el enésimo número de Fibonacci, dado n> 0.
Alguien, que no piensa en Memoization, inmediatamente piensa en algo simple y recursivo.
func fib (int n) {
si (n == 1 || n == 2)
retorno 1;
más
retorno (fib (n-1) + fib (n-2));
}
Parece estar bien ¿Correcto? Intente ejecutarlo en una PC doméstica normal con un procesador de ~ 3 GHz y 4 a 8 GB de RAM. Tome n como un número impar de 50 o 60. Usted puede ir y tomar una taza de café cuando este programa le dé la respuesta.
Porque preguntas ? ¿Qué tiene de malo este programa? Es un programa simple que se ejecuta primero mientras se estudia la recursión por primera vez.
La respuesta, radica en la complejidad. Este algo lleva tiempo exponencial. O (2 ^ n). Cuando ejecutas esto para una n más alta, los sentidos de una máquina de computadora se lanzan porque sigue calculando fib (Ns más bajas) repetidamente.
Si dibuja el árbol de recursión para las llamadas de función para este algo, verá cuántas llamadas repetidas se realizan.
Ahora, utilice un enfoque ascendente para este programa.
// Haz un poco de precalulación. es decir, memorizar primero.
int [] memo = new int [1000];
Arrays.fill (memo, 0);
memo [0] = memo [1] = 1;
// Hacer precalulación (es decir, Memoize), esto lleva O (n) tiempo.
precalc () {
para (int i = 2; i <1000; i ++) {
memo [i] = memo [i-1] + memo [i-2];
}
}
// Ahora esta función es un paseo de pastel que toma O (1) tiempo.
func fib (int n) {
memo de retorno [n-1];
}
Como puede ver, debido a la construcción de un diccionario, la complejidad se vuelve lineal, es decir, O (n) + O (1) = O (n). Ejecute esto para un rango superior, obtendrá el resultado al instante.
Ohh, lo entiendo, no estás impresionado. No es un ejemplo perfecto de DP.
Considere esto ahora:
Problema:
Dadas algunas denominaciones de monedas en la matriz denom [] = {1,3,5}; Encuentre el número mínimo de monedas requerido para hacer una suma de S = 11.
Inmediatamente saltas, lees esta pregunta y dices, esto se puede resolver fácilmente usando Greedy algo.
static int minCoins (int [] arr, int S) {
Arrays.sort (arr);
int cuenta = 0;
int N = S;
para (int j = a.size () - 1; j> = 0; j -) {
si (N> 0) {
cuenta + = N / arr [j];
N = N% arr [j];
}
}
si (N == 0)
cuenta de retorno;
más
volver -1;
}
Luce bien. Pero, ahora intente esto para denom [] = {1,10,25} y suma S = 40. Ohh, lamentablemente el codicioso algo bombardea.
Dicha pregunta se puede resolver correctamente para todas las entradas que utilizan DP.
static int countCoins (int [] monedas, int S) {
int [] resultado = nuevo int [S + 1];
Arrays.fill (resultado, 1000);
resultado [0] = 0;
para (int i = 1; i <= S; i ++) {
for (int j = 0; j <monedas.length; j ++) {
if (monedas [j] <= i && (resultado [i-monedas [j]] + 1 <resultado [i]))
resultado [i] = resultado [i-monedas [j]] + 1;
}
}
resultado devuelto [S];
}
Volviendo al “punto” de complejidad de O (n ^ 2).
Si un problema habla de calcular la longitud de la subsecuencia común más larga.
Dadas dos secuencias, encuentre la longitud de la subsecuencia común más larga presente en ambas. Una subsecuencia es una secuencia que aparece en el mismo orden relativo, pero no necesariamente contigua. Por ejemplo, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, etc. son subsecuencias de “abcdefg”. Entonces, una cadena de longitud n tiene 2 ^ n subsecuencias posibles diferentes.
/ * Una implementación recursiva ingenua del problema LCS * /
#include
#include
int max (int a, int b);
/ * Devuelve la longitud de LCS para X [0..m-1], Y [0..n-1] * /
int lcs (char * X, char * Y, int m, int n)
{
si (m == 0 || n == 0)
devuelve 0;
si (X [m-1] == Y [n-1])
devuelve 1 + lcs (X, Y, m-1, n-1);
más
return max (lcs (X, Y, m, n-1), lcs (X, Y, m-1, n));
}
La complejidad temporal del enfoque recursivo ingenuo anterior es O (2 ^ n) en el peor de los casos y el peor de los casos ocurre cuando todos los caracteres de X e Y no coinciden, es decir, la longitud de LCS es 0.
Teniendo en cuenta la implementación anterior, a continuación se muestra un árbol de recursión parcial para las cadenas de entrada “AXYT” y “AYZX”
lcs (“AXYT”, “AYZX”)
/ \
lcs (“AXY”, “AYZX”) lcs (“AXYT”, “AYZ”)
/ \ / \
lcs (“AX”, “AYZX”) lcs (“AXY”, “AYZ”) lcs (“AXY”, “AYZ”) lcs (“AXYT”, “AY”)
Tienes la idea del árbol de recursión.
Como podemos observar desde el árbol de recursión que muchos subproblemas se resuelven repetidamente, podemos resolverlos una vez y almacenar el resultado en algún lugar. De modo que si la próxima vez se produce un subproblema de este tipo, en lugar de calcularlo de nuevo, podemos hacer una búsqueda desde nuestro memo (diccionario).
/ * Solución DP del problema LCS * /
static int longestCommonSubSeq (char [] s1, char [] s2) {
int N = s1.length;
int [] [] dp = nuevo int [N + 1] [N + 1];
para (int i = 0; i <N; i ++) {
dp [0] [i] = dp [i] [0] = 0;
}
para (int i = 1; i <= N; i ++) {
para (int j = 1; j <= N; j ++) {
dp [i] [j] = max (dp [i-1] [j], dp [i] [j-1]);
if (s1 [i-1] == s2 [j-1]) {
dp [i] [j] = max (dp [i-1] [j-1] + 1, dp [i] [j]);
}
}
}
devolver dp [N] [N];
}
Esto se ejecuta en tiempo O (n ^ 2). Ahora, no hace falta ser un genio para darse cuenta de que 2 ^ n es mucho más pobre que O (n ^ 2).
