# La programación dinámica - Sitio: Ikusmira — enciclopedia en castellano de ciencias sociales y humanidades - URL canónica: https://ikusmira.org/p/la-programacion-dinamica/ - Categoría: Informática - Publicado: 2026-08-26 - Autoría: Josemari Sarasola Ledesma — Editor coordinador; Profesor titular de escuela universitaria, Universidad del País Vasco/Euskal Herriko Unibertsitatea - Perfiles del autor: https://ekoizpen-zientifikoa.ehu.eus/investigadores/127490/detalle, https://dialnet.unirioja.es/servlet/autor?codigo=333202 - Política editorial (autoría, revisión, correcciones, financiación): https://ikusmira.org/politica-editorial/ La **programación dinámica** (en inglés, *dynamic programming*) es una manera de resolver problemas que se descomponen en problemas más pequeños del mismo tipo, cuando esos problemas pequeños se repiten. La regla es una: resolver cada uno una sola vez y apuntar la respuesta, de modo que la segunda vez que haga falta se lea en lugar de calcularse. Lo de «programación» no tiene que ver con escribir código; en los años cincuenta la palabra significaba planificación, como en la programación lineal, y se ha quedado por costumbre. La figura de esta página usa el ejemplo más pequeño que lo enseña todo. Una escalera de *n* peldaños se sube de uno en uno o de dos en dos; de cuántas maneras distintas se puede llegar arriba. Para llegar al peldaño *n* se viene del *n* − 1 o del *n* − 2, así que las maneras de llegar a *n* son las de llegar a *n* − 1 más las de llegar a *n* − 2. Escrito tal cual, como una [función recursiva](https://ikusmira.org/p/la-recursividad/), el programa funciona, y la figura dibuja el árbol de llamadas que produce: cada rama vuelve a calcular escaleras que otra rama ya había calculado, y las repeticiones, pintadas del mismo color, son casi todo el árbol. Debajo, la misma cuenta hecha con una tabla de *n* casillas rellenada de izquierda a derecha, en la que cada casilla se escribe una vez. La diferencia no es de estilo sino de orden de magnitud. El árbol crece como una potencia: para diez peldaños tiene 177 nodos, para veinte, casi 22.000, y para cuarenta, más de 330 millones, con los que un ordenador tarda segundos en algo que debería ser instantáneo. La tabla tiene *n* casillas. Es el salto que [la notación O grande](https://ikusmira.org/p/la-notacion-o-grande/) describe como pasar de exponencial a lineal, y lo único que ha cambiado es que no se calcula dos veces lo mismo. Hay dos formas de conseguirlo. La primera, llamada memorización (*memoization*, con una sola «r», por memorándum), deja la función recursiva como está y le añade un diccionario donde mira antes de calcular y apunta después. La segunda construye la tabla desde los casos más pequeños hacia arriba, sin recursividad, como hace la figura; suele ser más rápida y gasta menos pila de llamadas, a cambio de obligar a pensar el orden en que se rellena. Para que la técnica funcione hacen falta dos condiciones, y Richard Bellman las formuló en la RAND Corporation a principios de los años cincuenta mientras estudiaba cómo tomar decisiones en varias etapas. La primera es que el problema grande se resuelva a partir de soluciones óptimas de problemas más pequeños, lo que llamó principio de optimalidad: el mejor camino de A a C que pasa por B contiene el mejor camino de A a B. La segunda es que esos problemas pequeños se repitan, porque si cada uno fuera distinto no habría nada que reutilizar. Bellman publicó la teoría en 1954 y el libro en 1957, y contó en su autobiografía de 1984 de dónde salió el nombre: el secretario de Defensa de la época, Charles Wilson, detestaba la palabra «investigación» y más aún «matemáticas», así que eligió «programación» por respetable y «dinámica» porque, decía, era imposible usarla en sentido peyorativo. La historia quizá esté adornada, pero el nombre se quedó. Lo que la escalera enseña en pequeño está en herramientas de uso diario. El corrector ortográfico que propone «ejemplo» cuando se escribe «ejmeplo» calcula la distancia de edición entre las dos palabras, el número mínimo de letras que hay que insertar, borrar o cambiar, con una tabla de dos dimensiones que Robert Wagner y Michael Fischer describieron en 1974; la misma tabla, con otros pesos, alinea dos secuencias de ADN. La función que compara dos versiones de un fichero en [el control de versiones](https://ikusmira.org/p/el-control-de-versiones/) busca la subsecuencia común más larga con una tabla parecida. El receptor de un teléfono móvil decodifica la señal con el algoritmo de Viterbi, que es programación dinámica sobre los estados posibles del emisor. Y TeX, el sistema de composición de Knuth, decide dónde cortar cada párrafo en líneas minimizando la fealdad total del párrafo entero, no de cada línea, con una tabla que recorre todos los puntos de corte posibles. [El algoritmo de Dijkstra](https://ikusmira.org/p/el-algoritmo-de-dijkstra/) también la cumple: la distancia a cada nodo se fija una vez y se reutiliza para calcular la de los siguientes. La técnica tiene límites. El primero es la memoria, porque la tabla hay que guardarla, y en problemas con muchas variables crece hasta no caber en ningún ordenador; Bellman bautizó eso también, la maldición de la dimensionalidad. El segundo es que no todo se descompone. Para [el problema del viajante](https://ikusmira.org/p/el-problema-del-viajante/), Michael Held y Richard Karp encontraron en 1962 una programación dinámica que lo resuelve en un tiempo del orden de *n*² por 2 elevado a *n*, muchísimo mejor que probar todas las rutas, pero exponencial igualmente, y sesenta años después sigue siendo el mejor método exacto general que se conoce. La programación dinámica no convierte lo imposible en fácil; convierte en fácil lo que solo parecía difícil porque se estaba repitiendo. Esa es la lección que vale fuera de la informática. Antes de calcular, preguntarse si esto ya se calculó; antes de empezar un problema grande, preguntarse de qué problemas pequeños se compone y cuáles de ellos se parecen entre sí. La escalera de la figura tiene, para treinta peldaños, más de un millón de maneras de subirse, y la tabla las cuenta en treinta sumas. [La recursividad](https://ikusmira.org/p/la-recursividad/) – [La notación O grande](https://ikusmira.org/p/la-notacion-o-grande/) – [El algoritmo de Dijkstra](https://ikusmira.org/p/el-algoritmo-de-dijkstra/) – [El problema del viajante](https://ikusmira.org/p/el-problema-del-viajante/) – [El control de versiones](https://ikusmira.org/p/el-control-de-versiones/) ## Fuentes - Richard Bellman — *The Theory of Dynamic Programming*, Bulletin of the American Mathematical Society 60 (6) (1954) — https://doi.org/10.1090/S0002-9904-1954-09848-8 - Richard Bellman — *Dynamic Programming*, Princeton University Press (1957) - Michael Held y Richard M. Karp — *A Dynamic Programming Approach to Sequencing Problems*, Journal of the Society for Industrial and Applied Mathematics 10 (1) (1962) — https://doi.org/10.1137/0110015 - Robert A. Wagner y Michael J. Fischer — *The String-to-String Correction Problem*, Journal of the ACM 21 (1) (1974) — https://doi.org/10.1145/321796.321811 - Richard Bellman — *Eye of the Hurricane: An Autobiography*, World Scientific (1984) --- Cómo citar: Sarasola, Josemari (2026). «La programación dinámica». Ikusmira. https://ikusmira.org/p/la-programacion-dinamica/ Índice del sitio para modelos: https://ikusmira.org/llms.txt