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.

🔗 Relacionados