Introducción

La programación dinámica es una técnica utilizada en la programación para resolver problemas complejos mediante la descomposición en subproblemas más pequeños y simples. Esta técnica es muy útil en la optimización de algoritmos con el objetivo de mejorar el rendimiento al reducir el tiempo y el espacio necesarios para completar una tarea. En este artículo, veremos cómo aplicar la programación dinámica en JavaScript.

Conceptos básicos de programación dinámica

La programación dinámica se utiliza para resolver problemas que tienen una estructura de subproblemas que se pueden resolver de manera recursiva. El objetivo es encontrar una solución óptima al problema global reduciéndolo a subproblemas más pequeños y resolviéndolos de manera recursiva. Para aplicar la programación dinámica, es necesario dividir el problema en subproblemas y almacenar los resultados de los subproblemas para su reutilización en futuras llamadas. Esto reduce el tiempo de ejecución de la función al evitar la repetición de cálculos innecesarios.

Top-down (memoization)

En la técnica top-down de programación dinámica, se recurre a la resolución de subproblemas de manera recursiva, pero almacena los resultados de los subproblemas para su reutilización. Este proceso se conoce como memoization y se utiliza para reducir la complejidad temporal de la resolución de problemas. En JavaScript, la memoization se puede implementar mediante la creación de una función que almacena en caché los resultados de los subproblemas y devuelve el resultado almacenado si el mismo subproblema se encuentra de nuevo. La implementación suele comenzar creando un objeto vacío donde se almacenan los resultados de los subproblemas y se comprueba si el resultado para un subproblema determinado ya se encuentra en la caché antes de llamar a la función recursiva.

Bottom-up (tabulation)

En la técnica bottom-up de programación dinámica, se resuelven los subproblemas de manera iterativa en lugar de hacerlo de manera recursiva. Los resultados de los subproblemas se almacenan en una tabla y se utilizan para resolver el problema global. La implementación suele comenzar creando una tabla de resultado que almacenará los resultados de los subproblemas. Luego, se completan los resultados de la tabla de manera iterativa, empezando por los subproblemas más pequeños y avanzando hacia el problema global. La técnica bottom-up también se conoce como tabulation y es especialmente útil cuando la solución del problema depende del resultado de subproblemas anteriores de manera secuencial.

Ejemplos de programación dinámica en JavaScript

Ejemplo top-down (memoization)

Un ejemplo común de programación dinámica es la forma de calcular el número de Fibonacci. La serie de Fibonacci es una sucesión de números en la que cada número es la suma de los dos números anteriores: 0, 1, 1, 2, 3, 5, 8, 13, 21, etc. El cálculo recursivo de la serie de Fibonacci puede ser ineficiente, ya que se calcula el mismo número varias veces. La técnica top-down de programación dinámica permite evitar estos cálculos innecesarios mediante la memoization. El siguiente código muestra un ejemplo de Fibonacci utilizando memoization en JavaScript: ``` function Fibonacci(n, cache = {}) { if (n in cache) return cache[n]; if (n <= 1) return n; cache[n] = Fibonacci(n - 1, cache) + Fibonacci(n - 2, cache); return cache[n]; } ``` La función Fibonacci toma un parámetro `n` que representa el índice de la sucesión de Fibonacci que se desea calcular. El parámetro `cache` es un objeto que almacena los resultados de los subproblemas para su reutilización. La función verifica si el resultado para el índice `n` ya se encuentra en la caché antes de llamar a la función recursiva. Si el resultado ya se encuentra en la caché, la función devuelve el resultado almacenado. De lo contrario, la función calcula el resultado recursivamente y lo almacena en la caché antes de devolverlo.

Ejemplo bottom-up (tabulation)

Un ejemplo de uso típico de la técnica bottom-up de programación dinámica es el cálculo del número mínimo de monedas necesarias para dar cambio. Supongamos que tenemos una cantidad `n` de dinero y un conjunto de monedas de diferentes denominaciones `coins`. Queremos determinar la cantidad mínima de monedas requeridas para dar cambio a la cantidad `n`. El siguiente código muestra un ejemplo de cálculo del número mínimo de monedas requeridas utilizando la técnica tabulation: ``` function minCoins(coins, n) { const table = Array(n + 1).fill(Infinity); table[0] = 0; for (let i = 1; i < table.length; i++) { for (let j = 0; j < coins.length; j++) { if (coins[j] <= i) { table[i] = Math.min(table[i], table[i - coins[j]] + 1); } } } return table[n]; } console.log(minCoins([1, 5, 10, 25], 63)); // 6 ``` La función `minCoins` toma dos parámetros: `coins`, un array que contiene las denominaciones de las monedas, y `n`, la cantidad de dinero que se desea dar cambio. La función devuelve el número mínimo de monedas requeridas para dar cambio a `n`. Se crea una tabla `table` de longitud `n + 1` y se le asigna el valor `Infinity` para cada posición. El valor de `table[0]` se establece en 0, ya que no se necesitan monedas para dar cambio a 0. Luego, se recorren todas las posiciones de la tabla `table` y se recorren las monedas `coins`. Si el valor de la moneda `coins[j]` no es mayor que la posición actual `i`, se calcula el número mínimo de monedas requeridas para dar cambio a `i` utilizando la fórmula: `table[i] = Math.min(table[i], table[i - coins[j]] + 1)`. Finalmente, se devuelve el valor de `table[n]`, que contiene el número mínimo de monedas requeridas para dar cambio a `n`.

Conclusión

La programación dinámica es una técnica poderosa y eficiente para resolver problemas en la programación. La técnica top-down (memoization) utiliza la recursión para resolver subproblemas y almacenar los resultados en caché para su reutilización. La técnica bottom-up (tabulation) utiliza una tabla para almacenar los resultados de los subproblemas y resuelve los subproblemas de manera iterativa. Ambas técnicas permiten reducir el tiempo de ejecución de las funciones al evitar cálculos innecesarios. En JavaScript, la implementación de la programación dinámica es sencilla y las funciones pueden ser reutilizadas en diferentes proyectos para resolver problemas similares. Es importante conocer los conceptos básicos de la programación dinámica y saber cuál técnica utilizar dependiendo del tipo de problema que se desea resolver.