El enfoque de programación dinámica es similar a dividir y vencer al dividir el problema en subproblemas más pequeños y posibles. Pero a diferencia de dividir y conquistar, estos subproblemas no se resuelven de forma independiente. Más bien, los resultados de estos subproblemas más pequeños se recuerdan y se usan para subproblemas similares o superpuestos.
La programación dinámica se usa cuando tenemos problemas, que se pueden dividir en subproblemas similares, de modo que sus resultados se puedan reutilizar. En su mayoría, estos algoritmos se utilizan para la optimización. Antes de resolver el subproblema disponible, el algoritmo dinámico intentará examinar los resultados de los subproblemas resueltos previamente. Las soluciones de subproblemas se combinan para lograr la mejor solución.
Como tal, la programación dinámica no es una estrategia para obtener la solución a un problema, sino para optimizar el uso de recursos utilizados para encontrar la respuesta a pesar el sacrificio principal del recuso espacial.
Principio de la optimalidad
Cuando hablamos de optimizar nos referimos a buscar alguna de las mejores soluciones de entre muchas alternativas posibles. Dicho proceso de optimización puede ser visto como una secuencia de decisiones que nos proporcionan la solución correcta. Si, dada una subsecuencia de decisiones, siempre se conoce cuál es la decisión que debe tomarse a continuación para obtener la secuencia óptima, el problema es elemental y se resuelve trivialmente tomando una decisión detrás de otra.
Manifestaciones de la programación dinámica
La programación dinámica es principalmente una optimización sobre la recursividad simple. Siempre que veamos una solución recursiva que tenga llamadas repetidas para las mismas entradas, podemos optimizarla usando la Programación dinámica. La idea es simplemente almacenar los resultados de los subproblemas, para que no tengamos que volver a calcularlos cuando sea necesario más adelante. Esta optimización simple reduce las complejidades del tiempo de exponencial a polinomial. Por ejemplo, si escribimos una solución recursiva simple para los números de Fibonacci, obtenemos una complejidad de tiempo exponencial y si la optimizamos almacenando soluciones de subproblemas, la complejidad del tiempo se reduce a lineal.
Algoritmo de Fibonacci utilizando programación dinámica
Podemos utilizar programación dinámica para optimizar el algoritmo de Fibonacci de tal manera que el Fibonacci de N número solo sea calculado una vez, esto para evitar repetir cálculos, hacer este procedimiento cambia la complejidad del algoritmo de exponencial a lineal, sin embargo, siempre se sacrificará el espacio de memoria que cueste hacer un arreglo de N+1 posiciones.
Para explicar la optimización del clásico algoritmo de Fibonacci usaremos Python, debido a que su sintaxis es casi idéntica al pseudocódigo.
Entradas y datos iniciales
El algoritmo recibe el número para cual se desea calcular el Fibonacci en un algoritmo principal, en este se crea un arreglo de tamaño n+1 y se inicializan sus posiciones en -1 excepto las posiciones 0 y 1, debido a que ya sabemos que el Fibonacci de 0 es 0 y el de 1 es 1. Después se llama la función auxiliar enviándole el número y el arreglo.
Función auxiliar y cálculo del Fibonacci
Como se mencionó anteriormente el algoritmo recibe el n y el arreglo de tamaño n+1, este algoritmo tiene una lógica muy simple, si el Fibonacci de un número no se ha calculado, lo mandamos a calcular una única vez y al final de la recursión simplemente calculamos el Fibonacci final basado en las posiciones del arreglo.
Bibliografía
Data Structures - Dynamic Programming - Tutorialspoint. Recuperado 30 de Julio 2020, de: https://www.tutorialspoint.com/data_structures_algorithms/dynamic_programming.htm
Dynamic Programming - GeeksforGeeks.Recuperado 30 Julio 2020, de: https://www.geeksforgeeks.org/dynamic-programming/#concepts
Programación dinámica - EcuRed. Recuperado 30 de Julio 2020, de: https://www.ecured.cu/Programaci%C3%B3n_din%C3%A1mica#Principio_de_optimalidad