Optimización divide y vencerás (DP)
Tema: Programación Dinámica · temarios: Syllabus OCI · Syllabus IOI
📍 Para profundizar: esta ficha amplía las clases de la Ruta de Aprendizaje. Puedes estudiarla cuando un problema requiera esta herramienta.
Qué hace
Acelera DPs dp[i][j] = min_k (dp[i-1][k] + cost(k,j)) cuando el k óptimo es monótono en j, recurriendo sobre rangos de j y de k.
Complejidad: O(capas · n log n) en vez de O(capas · n²).
Cuándo usarlo
Particionar en grupos minimizando costo, cuando opt(j) es no decreciente (suele cumplirse con la desigualdad de cuadrángulo).
Implementación recomendada (C++)
// dp[i][j]: mejor coste usando i grupos hasta j. opt(i,j) monótono en j.
int n; vector<vector<long long>> dp;
long long cost(int k, int j); // ⬅ la defines tú: costo del grupo (k, j], idealmente O(1) con prefijos
// (función normal y no std::function: se llama ~n log n veces por capa)
void solve(int i, int jl, int jr, int optl, int optr) {
if (jl > jr) return;
int jm = (jl + jr) / 2;
pair<long long,int> best = {LLONG_MAX, -1};
for (int k = optl; k <= min(jm, optr); k++)
best = min(best, {dp[i-1][k] + cost(k, jm), k});
dp[i][jm] = best.first;
int opt = best.second;
solve(i, jl, jm - 1, optl, opt);
solve(i, jm + 1, jr, opt, optr);
}⚠️ Notas
Hay que probar la monotonía del punto óptimo (o la desigualdad de cuadrángulo: cost(a,c) + cost(b,d) ≤ cost(a,d) + cost(b,c) para a ≤ b ≤ c ≤ d) antes de aplicarla. Se usa por capas, inicializando dp[0]: for (int i = 1; i <= capas; i++) solve(i, 0, n-1, 0, n-1);. La complejidad supone que cost() responde en O(1).