## 2.2.1 ELEMENTOS DE PROGRAMACIÓN DINÁMICA

La esencia de los algoritmos de programación dinámica es que cambian espacio por rapidez almacenando soluciones a subproblemas en lugar de volver a resolverlos.

Los elementos generales de cómo desarrollar una solución de programación dinámica para un problema son:

1. Por lo regular es útil atacar el problema “de arriba hacia abajo” como si fuéramos a desarrollar un algoritmo recursivo; determinamos cómo resolver un problema grande suponiendo que conocemos soluciones para problemas más pequeños.

2. Si es evidente que guardando resultados de problemas más pequeños podremos evitar cálculos repetidos, definimos el diccionario apropiado para guardar los resultados y caracterizamos claramente las entradas del diccionario. Hay que procurar que el identificador de las entradas del diccionario sea lo más conciso posible; así, el diccionario y el número de subproblemas serán pequeños.

3. Con base en el número de subproblemas (el tamaño máximo del diccionario es una cota superior) y el número de aristas del grafo de subproblemas, se puede analizar la complejidad del procedimiento de programación dinámica por su relación con la búsqueda primero en profundidad en el grafo de subproblemas.

4. Decidimos qué estructura de datos sería apropiada para el diccionario. En muchos casos lo mejor es un arreglo uni o bidimensional. En esos casos sencillos es posible eliminar la “abstracción” simplificando. Si necesitamos un diccionario más complejo (por ejemplo, porque los identificadores son demasiado ralos para que un arreglo simple resulte práctico), lo mejor podría ser ajustarnos a la división de tareas impuesta por la metodología de Tipo de Dato Abstracto (TDA).

5. Si es posible, analizamos la estructura del grafo de subproblemas e ideamos un orden más sencillo para calcular las entradas del diccionario. El requisito es que se calculen en algún orden topológico inverso. Entonces, todos los subproblemas de los que depende el subproblema actual ya se habrán calculado previamente.

6. Determinamos cómo obtener la solución del problema a partir de los datos del diccionario. El diccionario podría servir como entrada de otro algoritmo que extrae las opciones que dieron pie al costo óptimo. Puesto que el diccionario tiene datos para todos los subproblemas del grafo de subproblemas, por lo regular sólo un subconjunto pequeño de los datos tiene que ver con la solución óptima final.

La experiencia con la programación dinámica (y la recursión) ayuda a desarrollar una buena intuición respecto a qué funcionará mejor para diversos problemas.

###