## 2.2 PROGRAMACIÓN DINÁMICA

Frecuentemente para resolver un problema complejo se tiende a dividir este en subproblemas más pequeños, resolver estos últimos (recurriendo posiblemente a nuevas subdivisiones) y combinar las soluciones obtenidas para calcular la solución del problema inicial.

Puede ocurrir que la división natural del problema conduzca a un gran número de subejemplares idénticos. Si se resuelve cada uno de ellos sin tener en cuenta las posibles repeticiones, resulta un algoritmo ineficiente; en cambio si se resuelve cada ejemplar distinto una sola vez y se conserva el resultado, el algoritmo obtenido es mucho mejor.

Esta es la idea de la programación dinámica: no calcular dos veces lo mismo y utilizar normalmente una tabla de resultados que se va rellenando a medida que se resuelven los subejemplares.

La programación dinámica es un método ascendente. Se resuelven primero los subejemplares más pequeños y por tanto más simples. Combinando las soluciones se obtienen las soluciones de ejemplares sucesivamente más grandes hasta llegar al ejemplar original.

Ejemplo:
Consideremos el cálculo de números combinatorios. El algoritmo sería:

función C(n, k)
si k=0 o k=n entonces devolver 1
si no devolver C(n-1, k-1) + C(n-1, k)

Ocurre que muchos valores C(i, j), con i < n y j < k se calculan y recalculan varias veces. Un fenómeno similar ocurre con el algoritmo de Fibonacci.

La programación dinámica se emplea a menudo para resolver problemas de optimización que satisfacen el principio de optimalidad: en una secuencia óptima de decisiones toda subsecuencia ha de ser también óptima.

###