Tema
Programación dinámica
- Algoritmos
- Nivel intermedio
La programación dinámica resuelve un problema definiendo subproblemas que se solapan, ordenándolos y resolviendo cada uno una sola vez con una recurrencia sobre los ya resueltos.
Nombre en inglés
Dynamic programming
Intuición
El paso difícil no es programar, sino nombrar el subproblema: En cuanto se define bien qué significa cada casilla de la tabla, la recurrencia sale sola. El examen de CS 6515 pide tres cosas en este orden: La definición del subproblema en una oración, la recurrencia con sus casos base y el orden de llenado junto con el coste.
Fórmula
definir T[i] o T[i][j] ; escribir T en funcion de indices menores ; devolver la casilla pedida ; coste = numero de casillas por coste de cada casilla
Ejemplo resuelto
Para la subsecuencia común más larga de «ABC» y «AC» se define T[i][j] como la longitud de la mejor solución entre los i primeros caracteres de la primera cadena y los j primeros de la segunda. Si los caracteres coinciden, T[i][j] vale T[i-1][j-1] más 1; si no coinciden, vale el máximo de T[i-1][j] y T[i][j-1]. La tabla de 4 por 3 se llena por filas y la casilla final vale 2, que corresponde a «AC».
Errores frecuentes
- Definir el subproblema con palabras vagas: Decir que T[i] es la mejor solución hasta i no basta, ya que hay que precisar si incluye el elemento i o no, y de eso depende que la recurrencia cierre.
- Llenar la tabla en un orden que usa casillas todavía vacías: El orden de llenado forma parte de la solución y hay que justificarlo.
- Confundir la memoización con la programación dinámica ascendente: Las dos evitan recalcular, pero la versión recursiva puede desbordar la pila con entradas grandes.
Ejercicio
Se define T[i] como el número de formas de subir una escalera de i peldaños dando pasos de uno o de dos. Con T[0] igual a 1 y T[1] igual a 1, ¿cuánto vale T[5]?
Ver la solución
La recurrencia es T[i] igual a T[i-1] más T[i-2]. Se obtienen T[2] igual a 2, T[3] igual a 3, T[4] igual a 5 y T[5] igual a 8.
Respuesta: 8