La programación dinámica guarda la respuesta a una pregunta más pequeña para que las elecciones posteriores puedan reutilizarla. Empieza escribiendo qué significa un estado. Un recuento de rutas, un coste mínimo y un indicador de alcanzabilidad de sí o no necesitan valores base distintos aunque sus bucles se parezcan. Cero es un coste válido, pero no es un recuento válido para una ruta vacía que tiene que sembrar las rutas posteriores.
Ve de las dependencias al orden de iteración. Las fichas reutilizables pueden ampliar una y otra vez un total más pequeño. Una caja indivisible no: actualizar las sumas de subconjuntos hacia abajo impide usar esa caja dos veces. Para una subsecuencia estrictamente creciente, un conjunto compacto de mejores finales sustituye a una tabla de estados cuadrática.
Antes de programar, sigue la entrada no vacía más pequeña y la entrada vacía. Después de programar, explica por qué cada transición representa una elección válida y por qué no se pierde ninguna. El último ejercicio aplica la idea de estado a un reparto de carga en lugar de a un recuento de caminos.
Elige el significado de los estados y las transiciones para elecciones ordenadas, totales óptimos y alcanzabilidad.