Aprendiendo Dynamic Programming con JS porque el entrevistador me lo ordenó -parte 1

Cuando estas en este mundo hermoso del desarrollo de software normalmente en el lapso de la semana te llegan N cantidad de invitaciones para aplicar una vacante. Un día decidí aplicar a uno de estos puestos ya que me gustan los retos y desafiarme constantemente porque pues amo tener problemas.

La primeras fases normalmente consisten en retos simples, básicamente para asegurarse que no eres una papa.

En la segunda fase me pusieron un ejercicio el cual no entendí y mucho menos resolver y ya todos sabemos lo que sucede después

Nunca me había tocado un ejercicio de esa naturaleza (no se los digo porque ya no me acuerdo), después de ese pequeño fail como programador busque como resolver ese problema en san google y me topé con algunos ejemplos que decían que para resolver ese tipo de problemas usaban una estrategia llamada Dynamic Programming (DP).

A lo largo de mi vida como programador la mayoría de los problemas lo he resuelto usando la estrategia Divide And Conquer.

La DP es similar a la estrategia Divide And Conquer en el sentido de dividir el problema en sub-problemas, la única diferencia es que estos sub-problemas son dependientes y al ser resueltos el resultado es almacenado y reutilizado para no tener que re-calcular valores futuros y obtener un resultado de una manera más optima.

Tu al leer esa explicación

En un lenguaje mas de humanos puedo resumirlo en los siguientes puntos:

• Divides el problema hasta llegar a un caso base.
• Ese caso base te servirá para resolver los demás casos y estos a su vez otros.
• Los resultados son almacenados para no volver a calcularlos, a esto le llamamos memoization.

Hay que aclarar que la DP a veces hace uso de recursión pero no es obligatoria.

Para dejar esto claro vamos a resolver 2 ejercicios simples, el clásico problema de obtener el número N de la serie de fibonacci (dificultad fácil) y otro sobre obtener la máxima suma de números no adyacentes en un arreglo (dificultad media).

La serie de fibonacci

Es uno de los ejemplos más fáciles para entender los principios de la programación dinámica, ya que tenemos casos base ya definidos(0, 1) y con los resultados de estos podemos calcular los demás usando una formula que hace uso del cálculo de otros números en la serie que deben obtenerse para encontrar el resultado.

Formula:

f(n) = f(n-1) + f(n-2)

Casos base:

f(0) = 0

f(1) = 1

Ejemplo en el caso de f(2), la respuesta sería dada por la suma de f(2-1) y f(2–2)

En el caso cuando queremos resolver este problema de manera recursiva, nos enfrentaremos al detalle de repetir operaciones para cálculos que ya hemos hecho. Cuando n= 4 se sumarán f(3) y f(2), para calcular f(3), tienes que sumar f(2) y f(1) y así sucesivamente, si observas el árbol de llamadas a la función para sacar fibonacci te darás cuenta que calculamos 2 veces f(2).

Arbol de llamadas a función fibonacci

Esto crece exponencialmente con el incremento de n, para evitarlo hacemos uso de una técnica llamada memoization que consiste almacenar los resultados para ya no volver a hacer cálculos que ya hemos hecho(dependiendo del lenguaje sera el tipo de dato que uses ya sean sets, diccionarios, objetos, etc). En el siguiente código tienes un ejemplo de la función para obtener fibonacci sin memoization y con memoization. En un principio quizás no haya mucha diferencia de performance pero conforme n sea mayor la operación sera mas lenta.

Máxima suma de números no adyacentes en un arreglo

Para resolver este problema debes tener en cuenta que por adyacente se entiende como el item siguiente con respecto al item actual.

Ejemplo:

Arreglo A : [2 , 10, 11, 2], ArregloB: [20, 10, 1, 15]

En el arreglo A, la máxima suma es 13 (2 y 11) y en el arreglo B, la máxima suma es 35 (20 y 15).

Para resolver este problema debemos recorrer el arreglo y obtener los números no adyacentes para el elemento actual y el siguiente, un ejemplo :

Suma de número adyacentes

1. Tenemos el arreglo [10, 5, 20, 200, 10].
2. Tomamos el primer elemento que es 10.
3. Se busca la suma de los no adyacentes a partir de la posición de 10 los siguientes números son: 20, 200.
4. A partir de la posición de 20 se busca la suma des sus elementos no adyacentes, pero solo queda 10 este busca sus elementos no adyacentes pero al no tener se regresa a si mismo llegando al final de la recursión.
5. 10 se suma con 20, se regresa 30
6. 200 no tiene adyacente.
7. 200 es mayor que 30, se regresa 200.
8. El resultado de la suma de los adyacentes es 200 mas el elemento actual 10, es 210.
9. Tomamos el siguiente elemento que es 5.
10. Se busca la suma de los no adyacentes a partir de la posición de 5los siguientes números son: 200 y 10.
11. Como ya tenemos los resultados de las sumas de esos elementos estos se comparan y se regresa el mayor en este caso 200.
12. 200 se suma con 5.
13. 210 y 205 se comparan y se regresa 210.

Tu, yo y todos en este momento

Este es un ejemplo de la implementación , una vez que entendimos el problema lo único que hacemos es a partir de un indice calculamos sus números no adyacentes y los números no adyacentes del siguiente elemento, estos números harán lo mismo también ( bendita recursión). Al final solo comparamos la suma y obtendremos el resultado de la máxima suma.

Uno de las dificultades de esta técnica es que a veces es difícil depurar y puede ser un poco confuso, en extremo confuso pero la parte más difícil es entender el problema, una vez que lo entiendes el funcionamiento y la estructura de muchos algoritmos de DP es “similar”. Si estas interesado en hacer mas ejercicios de estos te recomiendo la plataforma de CodeFights.

Espero les haya gustado, la DP solo es un técnica mas en algunos problemas quizás no sea la ideal pero en otras funciona muy bien, es un tópico difícil pero con serenidad, paciencia y tacos puedes practicar hasta dominarla.

En próximos post resolveremos el problema de Coin Change y las N formas de subir una escalera usando DP.