Dividir e Conquistar DP

Dividir e Conquistar é uma otimização de programação dinâmica.

Pré-condições

Alguns problemas de programação dinâmica têm uma recorrência da forma: $$dp(i, j) = \min_{k \leq j} \{ dp(i - 1, k) + C(k, j) \}$$ onde $C(k, j)$ é alguma função de custo.

Deixe que $1 \leq i \leq n$ e $1 \leq j \leq m$, e avaliar $C$ leva tempo constante $O(1)$. A avaliação direta da recorrência acima é $O(n m^2)$. Existem $n \times m$ estados, e $m$ transições para cada estado.

Deixe que $opt(i, j)$ seja o valor de $k$ que minimiza a expressão acima. Se $opt(i, j) \leq opt(i, j + 1)$ para todo $i, j$, então podemos aplicar dividir-e-conquistar DP. Isso é conhecido como a condição de monotonicidade. O ideal "ponto de divisão" para um fixo $i$ é incrementando assim que $j$ aumenta.

Isso nos permite resolver todos os estados com mais eficiência. Calculamos $opt(i, j)$ para algum fixo $i$ e $j$. Então, para qualquer $j' < j$ sabemos que $opt(i, j') \leq opt(i, j)$. Isso significa que enquanto calculamos $opt(i, j')$, não precisaremos considerar tantos pontos de divisões!

Para minimizar o tempo de execução, aplicamos a ideia por trás de dividir e conquistar. Primeiro, calcule $opt(i, n / 2)$. Então, calcule $opt(i, n / 4)$, sabendo que é menos ou igual a $opt(i, n / 2)$ e $opt(i, 3 n / 4)$ sabendo que é maior que ou igual a $opt(i, n / 2)$. Recursivamente checando os limites inferiores e superiores de $opt$, alcançamos uma complexidade $O(m n \log n)$ de tempo de execução. Cada possível valor de $opt(i, j)$ apenas aparece em $\log n$ nós diferentes.

Não importa o quão "equilibrado" $opt(i, j)$ é. Em um fixo nível, cada valor de $k$ é usado pelo menos duas vezes, e há no máximo $\log n$ níveis.

Implementação Genérica

Embora a implementação varie com base no problema, aqui está um modelo bastante genérico. A função compute calcula uma linha $i$ de estados dp_cur, dada a linha anterior $i-1$ de estados dp_before. A função precisa ser chamada com compute(0, n-1, 0, n-1).

int n;   //número de estados
long long C(int i, int j);      //C é alguma função de custo
vector<long long> dp_before(n), dp_cur(n);

// calcular dp_cur[l], ... dp_cur[r] (inclusos)
void compute(int l, int r, int optl, int optr)
{
    if (l > r)
        return;
    int mid = (l + r) >> 1;
    pair<long long, int> best = {INF, -1};

    for (int k = optl; k <= min(mid, optr); k++) {
        best = min(best, {dp_before[k] + 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);
}

Algumas coisas para serem observadas

A maior dificuldade com problemas de Dividir e Conquistar DP é provar a monotonicidade de $opt$. Muitos problemas de Dividir e Conquistar DP podem também serem resolvidos com o truque do Convex Hull ou vice-versa. É útil conhecer e entender ambos!

Problemas

Recursos