DP (Programación Dinámica)


Tema:

La programación dinámica es un tema muy usual en las competencias de programación y a la vez una técnica que requiere de cierta práctica para empezar a dominarse. Bien empleada la programación dinámica puede ser muy útil para resolver problemas que requieran minimizar el tiempo de ejecución de su algoritmo y a la vez requieran checar muchas soluciones para encontrar la óptima.

Las "DP's" dividen un problema en sub-problemas es decir resuelven un "gran" problema partiendolo en problemas pequeños para así llegar a la solución. Suele relacionarse con la definición de recursividad pero no debe confundirse ya que a veces la programación dinámica requiere de la misma recursividad para emplearse.
Hay dos estilos (tipos tal vez) de programación dinámica la Top-Bottom y la Bottom-Top que son dos diferentes enfoques de ver las soluciones con DP's y la forma en como las programamos también. Para este problema usaremos Top-Bottom (Recursiva).
Lo primero que hay que hacer para resolver un problema bajo DP es ver y analizar que posibles "estados" que tendrá nuestra función dp();
Para ello usaré como ejemplo un problema de COJ llamado 

Link del problema: Coin Change
Dificultad: Fácil

Problema:

Este problema consiste a grandes rasgos en decir de cuantas maneras podemos representar un numero $N$ con $0<= N <= 10,000$, con 5 tipos de monedas de cambio (50,25,10,5 y 1) por ejemplo el caso de prueba que viene en la página
Con dinero = 11 ¿De cuántas formas se puede expresar?


Solución:
1° 1+1+1+1+1+1+1+1+1+1+1 = 11 
2° 5+5+1 = 11 
3° 1+1+1+1+1+1 + 5 = 11
4° 10 + 1 = 11
Para este caso es evidente que la solución es 4 porque solo existen 4 maneras diferentes de representar nuestro número N.

Paso 1 (Identificar los estados de nuestra dp() ): 

-¿De que estados o variables depende?
Para este problema necesitamos tanto la cantidad de 'dinero' que llevamos hasta el momento y además que 'monedas' utilizamos.

int dp(int dinero,int i);

además de devolver el valor que procese nuestra dp() como int

Paso 2 (Decisiones: "Tomar o no tomarlo")

Esta parte de la dp() es muy importante ya que de aquí deriva el buen funcionamiento de la misma

-¿Qué decisiones podemos establecerle a este problema?

Supongamos que tenemos un arreglo cambios de la siguiente manera:
int cambios[] = {50,25,10,5,1};
Además supongamos que tenemos nuestro total de dinero y cada que tomemos o no un cambio[] se lo restaremos al total de dinero entonces sabremos cuando frenar la dp(); y saber que ya hemos procesado todo así:

if(dinero==0)
   return 1;

Como caso base de la DP quiere decir que ya le restamos todo a nuestro dinero entonces para ese entonces ya abremos tomado todas las decisiones 
if(dinero!=0 && i==5)
   return 0;
Es otra decisión pues quiere decir que terminamos de recorrer nuestro arreglo de monedas pero que no llegamos a nuestro dinero==0 o sea que no quedó justa la resta de los dineros.

Ahora las decisiones tienen que ver con que el número del arreglo no sea mayor a nuestro dinero, SI ES MAYOR NO LO TOMAMOS y avanzamos al siguiente elemento SI ES MENOR O IGUAL lo tomamos y se lo restamos a nuestro dinero OJO (mandamos ambas probabilidades tomarlo y no tomarlo) para que se realice el árbol y tome todas las posibilidades...
if(cambios[i]>dinero)
     return dp(dinero,i+1);

  if (cambios[i] <= dinero) 
     return dp(dinero - cambios[i],i) + dp(dinero,i+1);

Esto tiene una complejidad O($2^N$) así que haría falta memorizarlo para hacerlo pueden checar el siguiente enlace donde explico en mi blog como memorizar (memoizar) una función recursiva y eso nos reducirá la complejidad de la siguiente DP a O($n^2$) y aquí ya la función dp() memorizada:

 int dp(int dinero,int i){

   if(memo[dinero][i]!=-1)
      return memo[dinero][i];
   if(dinero==0)
      return 1;
   if(dinero==0 && i==5)
      return 1;

   if(i==5)
      return 0;

   if(cambios[i]>dinero)
      return memo[dinero][i] = dp(dinero,i+1);

   if (cambios[i] <= dinero) 
      return memo[dinero][i] = dp(dinero - cambios[i],i) + dp(dinero,i+1);
}
Esta es una DP sencilla pero en sí mejorar y perfeccionar esta técnica requiere mucha práctica aunque seguro hay un AC con este código, así que eso es todo por esta sesión. 

Por: Adrián Fernández @ferprogramming

No hay comentarios on "DP (Programación Dinámica)"

Leave a Reply