Optimización de Knuth
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 de intervalo dp[l][r] = min_{l<=k<r}(dp[l][k]+dp[k+1][r]) + cost(l,r) usando que el k óptimo está acotado por los óptimos vecinos.
Complejidad: O(n²) en vez de O(n³).
Cuándo usarlo
DP de intervalos con monotonía demostrada de los cortes óptimos; por ejemplo, fusión de pesos no negativos con costo igual a su suma.
Implementación recomendada (C++)
int n; vector<vector<long long>> dp, opt;
long long cost(int l, int r); // ⬅ la defines tú: costo de juntar [l, r], O(1) con prefijos
void knuth() {
for (int i = 0; i < n; i++) { dp[i][i] = 0; opt[i][i] = i; }
for (int len = 2; len <= n; len++)
for (int l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
dp[l][r] = LLONG_MAX;
long long c = cost(l, r); // no depende de k: fuera del bucle
for (int k = opt[l][r-1]; k <= min(r - 1, (int)opt[l+1][r]); k++) {
long long val = dp[l][k] + dp[k+1][r] + c;
if (val < dp[l][r]) { dp[l][r] = val; opt[l][r] = k; }
}
}
}⚠️ Notas
Debes justificar opt[l][r-1] ≤ opt[l][r] ≤ opt[l+1][r], usando siempre el mismo desempate (aquí el menor k). Condiciones suficientes para esta recurrencia: para a ≤ b ≤ c ≤ d, cost(b,c) ≤ cost(a,d) (monotonía por inclusión) y cost(a,c)+cost(b,d) ≤ cost(a,d)+cost(b,c) (desigualdad de cuadrángulo). La suma de pesos no negativos cumple ambas. La desigualdad sola NO basta: cost(l,r)=a[l]+b[r], a=[0,0,17,0], b=[12,6,13,0], la cumple con igualdad pero viola inclusión; este código da 19 y la DP cúbica da 13. Si no puedes demostrar las condiciones ni la monotonía de opt, conserva la DP cúbica. Inicializa dp y opt como matrices n×n; las sumas deben caber en long long.