Tema 3
Programación dinámica
Patrón de examen
Si la recursión ingenua recalcula los mismos subproblemas, aplica DP. Identifica el estado (qué información necesitas) y la transición (cómo pasar de estados anteriores al actual).
Explicación
¿Qué es la Programación Dinámica (DP)?
Resolver un problema dividiéndolo en subproblemas que se solapan, guardando los resultados para no recalcularlos.
Dos ingredientes necesarios:
- Subestructura óptima: la solución óptima se construye a partir de soluciones óptimas de subproblemas
- Subproblemas solapados: el mismo subproblema se resuelve múltiples veces
Top-down vs Bottom-up
- Top-down: recursión + memoización (guardar en arreglo)
- Bottom-up: llenar una tabla desde los casos base hacia arriba (iterativo)
Patrones clásicos
Knapsack 0/1
Para cada ítem decide: incluir o no.
dp[i][w] = max valor con los primeros i ítems y capacidad w
dp[i][w] = max(dp[i-1][w], dp[i-1][w-peso[i]] + valor[i])
Longest Common Subsequence (LCS)
dp[i][j] = LCS de A[0..i] y B[0..j]
si A[i]==B[j]: dp[i][j] = dp[i-1][j-1] + 1
sino: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Longest Increasing Subsequence (LIS)
dp[i] = longitud del LIS que termina en el índice i