Skip to Content
CTRL K

DP de divide y vencerás

Divide and Conquer es una optimización de programación dinámica.

Precondiciones

Algunos problemas de programación dinámica tienen una recurrencia de esta forma:

dp(i,j)=min⁡0≤k≤jdp(i−1,k−1)+C(k,j) dp(i, j) = \min_{0 \leq k \leq j} \{ dp(i - 1, k - 1) + C(k, j) \}

donde C(k,j)C(k, j) es una función de costo y dp(i,j)=0dp(i, j) = 0 cuando j<0j \lt 0.

Digamos 0≤i<m0 \leq i \lt m y 0≤j<n0 \leq j \lt n, y evaluar CC toma O(1)O(1) tiempo. Entonces la evaluación directa de la recurrencia de arriba es O(mn2)O(m n^2). Hay m×nm \times n estados, y nn transiciones por cada estado.

Sea opt(i,j)opt(i, j) el valor de kk que minimiza la expresión de arriba. Asumiendo que la función de costo satisface la desigualdad del cuadrángulo, podemos mostrar que opt(i,j)≤opt(i,j+1)opt(i, j) \leq opt(i, j + 1) para todos los i,ji, j. Esto se conoce como la condición de monotonía. Entonces, podemos aplicar DP de divide y vencerás. El “punto de corte” óptimo para un ii fijo crece a medida que jj crece.

Esto nos permite resolver todos los estados de forma más eficiente. Digamos que computamos opt(i,j)opt(i, j) para algún ii y jj fijos. Entonces para cualquier j′<jj’ < j sabemos que opt(i,j′)≤opt(i,j)opt(i, j’) \leq opt(i, j). Esto significa que al computar opt(i,j′)opt(i, j’), no tenemos que considerar tantos puntos de corte.

Para minimizar el tiempo de ejecución, aplicamos la idea detrás de divide y vencerás. Primero, computamos opt(i,n/2)opt(i, n / 2). Después, computamos opt(i,n/4)opt(i, n / 4), sabiendo que es menor o igual que opt(i,n/2)opt(i, n / 2) y opt(i,3n/4)opt(i, 3 n / 4) sabiendo que es mayor o igual que opt(i,n/2)opt(i, n / 2). Llevando recuenta de forma recursiva las cotas inferiores y superiores de optopt, llegamos a un tiempo de ejecución O(mnlog⁡n)O(m n \log n). Ver el código de abajo para los detalles de implementación.

Para demostrar la complejidad de divide y vencerás, primero nótese que hay O(log⁡n)O(\log{n}) niveles en la recursión. Afirmamos que se hacen O(n)O(n) pasos en cada nivel. Sea la longitud total de los intervalos opt\text{opt} (denotados por optloptl y optroptr en el código) en el kk-ésimo nivel SkS_k, y observemos que cada vez que un intervalo del nivel kk de longitud xx se parte, el/los intervalo(s) resultante(s) tienen longitud total a lo sumo x+1x + 1. Además, en el nivel kk, se realizan a lo sumo 2k2^k cortes, así que Sk+1≤Sk+2kS_{k + 1} \leq S_k + 2^k. Aplicando la cota por inducción con S0=nS_0 = n da que para cada nivel kk,

Sk<n+2k∈O(n). S_k < n + 2^k \in O(n).

Así, la complejidad de cada divide y vencerás es O(nlog⁡n)O(n\log{n}), y la complejidad de todo el cómputo de DP es O(mnlog⁡n)O(mn\log{n}).

Implementación genérica

Aunque la implementación varía según el problema, acá hay un template bastante genérico. La función compute computa una fila ii de estados dp_cur, dada la fila anterior i−1i-1 de estados dp_before. Hay que llamarla con compute(0, n-1, 0, n-1). La función solve computa m filas y devuelve el resultado.

int m, n;
vector<long long> dp_before, dp_cur;

long long C(int i, int j);

// compute dp_cur[l], ... dp_cur[r] (inclusive)
void compute(int l, int r, int optl, int optr) {
    if (l > r)
        return;

    int mid = (l + r) >> 1;
    pair<long long, int> best = {LLONG_MAX, -1};

    for (int k = optl; k <= min(mid, optr); k++) {
        best = min(best, {(k ? dp_before[k - 1] : 0) + C(k, mid), k});
    }

    dp_cur[mid] = best.first;
    int opt = best.second;

    compute(l, mid - 1, optl, opt);
    compute(mid + 1, r, opt, optr);
}

long long solve() {
    dp_before.assign(n,0);
    dp_cur.assign(n,0);

    for (int i = 0; i < n; i++)
        dp_before[i] = C(0, i);

    for (int i = 1; i < m; i++) {
        compute(0, n - 1, 0, n - 1);
        dp_before = dp_cur;
    }

    return dp_before[n - 1];
}

Cosas a tener en cuenta

La mayor dificultad de los problemas de DP de divide y vencerás es demostrar la monotonía de optopt. Un caso especial en el que esto vale es cuando la función de costo satisface la desigualdad del cuadrángulo, es decir, C(a,c)+C(b,d)≤C(a,d)+C(b,c)C(a, c) + C(b, d) \leq C(a, d) + C(b, c) para todos los a≤b≤c≤da \leq b \leq c \leq d. Muchos problemas de DP de divide y vencerás también se pueden resolver con el Convex Hull trick o viceversa. ¡Es útil conocer y entender ambos!

Problemas de práctica

Referencias

Divide y vencerás - DPDP de suma sobre subconjuntos