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

🇨🇱 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.

ProblemaCompetenciaDificultad
El mejor camino2021 Nacional🟢 fácil
Parkour2022 Nacional🟢 fácil
Naruto vs Sasuke pelea completa (español latino)2017 Clasificatoria🟡 media
Alcohol Gel2021 Regional🟡 media
Descenso en parapente2021 Regional🔴 difícil
Galletas2025 Nacional🔴 difícil
Dedos Rápidos2017 Clasificatoria🔴 difícil
La biblioteca perdida de la cultura Chipotle2018 Nacional🔴 difícil
La torre de la maldad2021 Nacional🔴 difícil
Aplausómetro2024 Nacional🔴 difícil
Los Fideos de María2025 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.

ProblemaAñoMedia (puntos parciales)Lograron 100
Nile202468/10035%
Paint By Numbers201664/10029%
Mosaic202459/10025%
Boxes with souvenirs201544/10030%
Catfish Farm202234/10014%
Festival202532/1004%
Dungeons Game202130/1004%
Wiring201726/10014%
Digital Circuit202225/10015%
Soccer Stadium202323/100<1%
Packing Biscuits202023/10010%
Closing Time202323/1003%
Meetings201822/1000%
Monuments202620/100<1%
Aliens201618/100<1%
Tree202418/1001%
Beech Tree202315/100<1%
Toy Train201710/1001%
Hieroglyphs20245/100<1%