La programación dinámica, cuando se refiere al campo de la informática, describe un grupo de algoritmos informáticos similares destinados a resolver problemas complejos dividiendo el problema en conjuntos de problemas más pequeños. Creada por primera vez por Richard Bellman en la década de 1950, la programación dinámica trabaja con problemas que son subproblemas superpuestos o subestructuras óptimas. Para comprender cómo funciona la programación dinámica, es mejor comprender el concepto detrás de estos dos términos.
Los subproblemas superpuestos describen ecuaciones complicadas que, cuando se dividen en conjuntos más pequeños de ecuaciones, reutilizan partes de las ecuaciones más pequeñas más de una vez para llegar a una respuesta. Por ejemplo, una ecuación matemática indicada para calcular todos los resultados posibles usando un conjunto de números puede calcular el mismo resultado varias veces mientras calcula otros resultados solo una vez. La programación dinámica le diría a este problema que después de calcular el resultado la primera vez, debería guardar ese resultado y luego introducir la respuesta en la ecuación en lugar de volver a calcularla. Cuando se trata de procesos y ecuaciones largos y complejos, esto ahorra tiempo y crea una solución más rápida con muchos menos pasos.
Las subestructuras óptimas crean una solución al encontrar la mejor respuesta a todos los subproblemas y luego crear la mejor respuesta general. Después de dividir un problema complejo en problemas más pequeños, la computadora utiliza un sistema matemático para determinar cuál es la mejor respuesta para cada problema. Calcula la respuesta al problema original a partir de las respuestas más pequeñas. Existen defectos en este proceso. Si bien ofrece la solución que funciona mejor matemáticamente, puede ser o no la mejor solución en la vida real, según el tipo de problema y cómo se relaciona con el mundo real.
Durante cualquiera de estas operaciones, el algoritmo de programación dinámica intenta encontrar el camino más corto hacia la solución. Puede tomar uno de dos enfoques para hacer esto. El enfoque de arriba hacia abajo divide la ecuación en ecuaciones más pequeñas y reutiliza las respuestas para estas ecuaciones cuando es necesario. El enfoque de abajo hacia arriba intenta resolver el valor matemático más pequeño después de descomponer la ecuación y luego se abre camino hacia el más grande desde allí. Ambos enfoques ahorran tiempo, pero la programación dinámica solo funciona cuando el problema original se puede dividir en ecuaciones más pequeñas que en algún momento se reutilizan para resolver la ecuación.