Programación Dinámica
DP clásica, en árboles, bitmask, optimizaciones.
Volver a los 11 temas · Referencia · temarios: Syllabus OCI · Syllabus IOI.
📍 Clases relacionadas: módulos 14 · 22 de la Ruta de Aprendizaje.
📋 En el temario OCI: solo en la fase Nacional (⊗), como introducción.
DP es armar la respuesta grande combinando respuestas de subproblemas que se repiten, y guardarlas para no recalcularlas. Aparece cuando piden contar de cuántas formas o el mejor de algo que se construye por etapas.
📌 Qué abarca
- El vocabulario: estado (qué describe un subproblema), transición (cómo se arma desde estados menores), caso base y orden de llenado. Sin esas cuatro palabras no se puede leer ninguna solución de DP.
- DP clásica: mochila, LIS, LCS, intervalos, en grilla.
- DP bitmask (sobre subconjuntos) y DP en dígitos.
- DP en árboles (ver Árboles).
- Optimizaciones: convex hull trick, Knuth-Yao, divide & conquer optimization, Aliens trick (Lagrangian / búsqueda paramétrica).
⛔ Fuera del syllabus IOI
- La DP no tiene exclusiones propias, pero: se desalientan problemas donde la optimización es un paso mecánico final, y debe poder probarse que la técnica aplica. Acelerar convoluciones con FFT está fuera (es FFT).
🎯 En competencia
En la OCI — Entra en la Nacional en sus primeros modelos: Fibonacci con memoria, caminos en una grilla, subset-sum chico. En la Regional no se exige, aunque algunos problemas regionales admiten una DP sencilla como solución alternativa. En este vault hay 11 problemas OCI del tema (3 de fases regionales, 6 de fases nacionales y 2 de clasificatorias IOI); están en la tabla de abajo.
En la IOI — Lo difícil es definir el estado. Casi siempre hay puntos por una DP O(N²) “lenta” antes de la versión optimizada: impleméntala primero para asegurar subtareas.
⚠️ La trampa típica
Elegir un estado que no cabe: estados × trabajo por transición es el costo real, y estados también es la memoria. Si tu tabla no entra en 256 MB, el estado está mal elegido, no el lenguaje (Complejidad computacional).
⚙️ Algoritmos y técnicas
- Aliens trick (optimización lagrangiana)
- Convex hull trick (Li Chao)
- DP con bitmask
- DP de intervalos
- Kadane (subarreglo de suma máxima)
- Mochila 0-1
- Optimización de Knuth
- Optimización divide y vencerás (DP)
- Recursión y memoización
- Subsecuencia creciente más larga (LIS)
🇨🇱 Problemas OCI (en español)
Empieza por acá: son problemas oficiales chilenos, con enunciado en español y mirror para enviar. Consulta la orientación de estudio al comienzo de esta página. La dificultad orienta la elección, pero no garantiza una solución completa.
| Problema | Competencia | Dificultad |
|---|---|---|
| El mejor camino | 2021 Nacional | 🟢 fácil |
| Parkour | 2022 Nacional | 🟢 fácil |
| Naruto vs Sasuke pelea completa (español latino) | 2017 Clasificatoria | 🟡 media |
| Alcohol Gel | 2021 Regional | 🟡 media |
| Descenso en parapente | 2021 Regional | 🔴 difícil |
| Galletas | 2025 Nacional | 🔴 difícil |
| Dedos Rápidos | 2017 Clasificatoria | 🔴 difícil |
| La biblioteca perdida de la cultura Chipotle | 2018 Nacional | 🔴 difícil |
| La torre de la maldad | 2021 Nacional | 🔴 difícil |
| Aplausómetro | 2024 Nacional | 🔴 difícil |
| Los Fideos de María | 2025 Regional | 🔴 difícil |
🌍 Problemas IOI
De más abordable a más duro, según el puntaje promedio que sacaron los competidores: una media alta sugiere más puntos parciales accesibles, no más soluciones completas. Consulta también el porcentaje de 100 y los prerrequisitos.
| Problema | Año | Media (puntos parciales) | Lograron 100 |
|---|---|---|---|
| Nile | 2024 | 68/100 | 35% |
| Paint By Numbers | 2016 | 64/100 | 29% |
| Mosaic | 2024 | 59/100 | 25% |
| Boxes with souvenirs | 2015 | 44/100 | 30% |
| Catfish Farm | 2022 | 34/100 | 14% |
| Festival | 2025 | 32/100 | 4% |
| Dungeons Game | 2021 | 30/100 | 4% |
| Wiring | 2017 | 26/100 | 14% |
| Digital Circuit | 2022 | 25/100 | 15% |
| Soccer Stadium | 2023 | 23/100 | <1% |
| Packing Biscuits | 2020 | 23/100 | 10% |
| Closing Time | 2023 | 23/100 | 3% |
| Meetings | 2018 | 22/100 | 0% |
| Monuments | 2026 | 20/100 | <1% |
| Aliens | 2016 | 18/100 | <1% |
| Tree | 2024 | 18/100 | 1% |
| Beech Tree | 2023 | 15/100 | <1% |
| Toy Train | 2017 | 10/100 | 1% |
| Hieroglyphs | 2024 | 5/100 | <1% |