A programação dinâmica divide um problema em fases, representadas por estados, e decide a melhor transição entre eles. Três propriedades são essenciais:

• Estado, fase e decisão: o estado resume o passado, a fase indica o progresso e a decisão escolhe a melhor transição.
• Sobreposição de subproblemas: a mesma subexpressão aparece repetidamente, permitindo reutilização.
• Sem efeito posterior: o futuro só depende do estado atual, não de como se chegou até ele.
• Subestrutura ótima: a solução ótima global é construída a partir de soluções ótimas de subproblemas.

LCS, LIS e Triângulo Numérico

Subsequência Comum Mais Longa (LCS)

Dadas duas sequências seqA e seqB, a LCS busca o maior comprimento de uma subsequência presente em ambas. Define-se memo[i][j] como o tamanho da LCS entre os prefixos seqA[0..i-1] e seqB[0..j-1].

int tamanhoA, tamanhoB;
char seqA[MAX], seqB[MAX];
int memo[MAX][MAX];

int calcularLCS() {
    for (int i = 1; i <= tamanhoA; i++) {
        for (int j = 1; j <= tamanhoB; j++) {
            if (seqA[i - 1] == seqB[j - 1]) {
                memo[i][j] = memo[i - 1][j - 1] + 1;
            } else {
                memo[i][j] = max(memo[i - 1][j], memo[i][j - 1]);
            }
        }
    }
    return memo[tamanhoA][tamanhoB];
}

Subsequência Crescente Mais Longa (LIS)

A LIS encontra a maior subsequência em que cada elemento é maior que o anterior. A abordagem básica usa memo[i] como o tamanho da maior subsequência crescente terminando em v[i].

int n;
int v[MAX];
int memo[MAX];

int calcularLIS() {
    int melhor = 0;
    for (int i = 0; i < n; i++) {
        memo[i] = 1;
        for (int j = 0; j < i; j++) {
            if (v[j] < v[i]) {
                memo[i] = max(memo[i], memo[j] + 1);
            }
        }
        melhor = max(melhor, memo[i]);
    }
    return melhor;
}

Triângulo Numérico

Dado um triângulo de inteiros não negativos, deseja-se o caminho de maior soma do topo até a base, movendo-se sempre para baixo ou para a diagonal inferior direita.

const int MAXN = 105;
int triangulo[MAXN][MAXN];
int soma[MAXN][MAXN];

int resolverTriangulo(int linhas) {
    for (int i = linhas; i >= 1; i--) {
        for (int j = 1; j <= i; j++) {
            if (i == linhas) {
                soma[i][j] = triangulo[i][j];
            } else {
                soma[i][j] = triangulo[i][j] + max(soma[i + 1][j], soma[i + 1][j + 1]);
            }
        }
    }
    return soma[1][1];
}

Problemas da Mochila

Mochila 0-1

Cada item pode ser escolhido no máximo uma vez. Seja dp[i][c] o maior valor obtido com os primeiros i itens e capacidade c.

int qtdItens, capacidade;
int peso[MAX], utilidade[MAX];
int dp[2][MAX];

int mochila01() {
    memset(dp, 0x80, sizeof(dp));
    dp[0][0] = 0;
    for (int i = 1; i <= qtdItens; i++) {
        int atual = i & 1;
        int anterior = 1 - atual;
        for (int c = 0; c <= capacidade; c++) {
            dp[atual][c] = dp[anterior][c];
            if (c >= peso[i]) {
                dp[atual][c] = max(dp[atual][c], dp[anterior][c - peso[i]] + utilidade[i]);
            }
        }
    }
    return *max_element(dp[qtdItens & 1], dp[qtdItens & 1] + capacidade + 1);
}

Com uma única dimensão, percorre-se a capacidade de trás para frente para evitar reutilização do mesmo item:

int dpUnid[MAX];

int mochila01Compacta() {
    memset(dpUnid, 0x80, sizeof(dpUnid));
    dpUnid[0] = 0;
    for (int i = 1; i <= qtdItens; i++) {
        for (int c = capacidade; c >= peso[i]; c--) {
            dpUnid[c] = max(dpUnid[c], dpUnid[c - peso[i]] + utilidade[i]);
        }
    }
    return *max_element(dpUnid, dpUnid + capacidade + 1);
}

Mochila Completa

Cada item pode ser escolhido quantas vezes forem necessárias. A transição é similar, mas o loop de capacidade deve ser crescente, permitindo múltiplas escolhas do mesmo item.

int mochilaCompleta() {
    memset(dpUnid, 0x80, sizeof(dpUnid));
    dpUnid[0] = 0;
    for (int i = 1; i <= qtdItens; i++) {
        for (int c = peso[i]; c <= capacidade; c++) {
            dpUnid[c] = max(dpUnid[c], dpUnid[c - peso[i]] + utilidade[i]);
        }
    }
    return *max_element(dpUnid, dpUnid + capacidade + 1);
}

Mochila Múltipla e Agrupada

Na mochila múltipla, cada item possui uma quantidade limite. Uma técnica eficiente é a decmoposição binária, transformando quantidades em grupos de potências de dois e reduzindo o problema a 0-1.

Na mochila agrupada, os itens são divididos em grupos e deve-se escolher no máximo um item de cada grupo. O loop do grupo deve ser o mais externo, e o loop dos itens, o mais interno, para evitar seleções múltiplas dentro do mesmo grupo.

// Mochila agrupada
int f[MAX];
memset(f, 0x80, sizeof(f));
f[0] = 0;

for (int g = 1; g <= numGrupos; g++) {
    for (int c = capacidade; c >= 0; c--) {
        for (auto item : grupo[g]) {
            if (c >= item.peso) {
                f[c] = max(f[c], f[c - item.peso] + item.valor);
            }
        }
    }
}

Programação Dinâmica em Intervalos

Em DP de intervalos, o comprimento do intervalo funciona como a fase principal. Considere o problema de união de pedras, onde se deseja minimizar o custo total para agrupar todas as pedras.

int pedras[MAX];
int prefixo[MAX];
int custo[MAX][MAX];

int uniaoPedras(int n) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            custo[i][j] = (i == j) ? 0 : INF;
        }
    }
    for (int t = 1; t <= n; t++) prefixo[t] = prefixo[t - 1] + pedras[t];

    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            for (int k = l; k < r; k++) {
                custo[l][r] = min(custo[l][r], custo[l][k] + custo[k + 1][r]);
            }
            custo[l][r] += prefixo[r] - prefixo[l - 1];
        }
    }
    return custo[1][n];
}

Programação Dinâmica em Árvores

Em uma árvore, a transição ocorre entre um nó e seus filhos. Exemplo: escolher convidados para uma festa onde um funcionário e seu superior direto não podem ambos comparecer.

vector<int> filhos[MAX];
int felicidade[MAX];
int resultado[MAX][2];

void dfs(int u) {
    resultado[u][0] = 0;
    resultado[u][1] = felicidade[u];
    for (int v : filhos[u]) {
        dfs(v);
        resultado[u][0] += max(resultado[v][0], resultado[v][1]);
        resultado[u][1] += resultado[v][0];
    }
}

int main() {
    int n, raiz;
    // leitura da árvore ...
    dfs(raiz);
    return max(resultado[raiz][0], resultado[raiz][1]);
}

Variação: Mochila em Árvore

Cada nó da árvore tem um custo e um benefício. Deseja-se escolher um conjunto de nós respeitando uma restrição de capacidade, com a condição de que, se um nó é escolhido, seu caminho até a raiz também deve ser considerado.

int qtd, limite;
int credito[MAX];
int memoArvore[MAX][MAX];

void dpMochilaArvore(int u) {
    for (int v : filhos[u]) {
        dpMochilaArvore(v);
        for (int c = limite; c >= 0; c--) {
            for (int k = 0; k <= c; k++) {
                memoArvore[u][c] = max(memoArvore[u][c],
                                       memoArvore[u][c - k] + memoArvore[v][k]);
            }
        }
    }
    if (u != 0) {
        for (int c = limite; c > 0; c--) {
            memoArvore[u][c] = memoArvore[u][c - 1] + credito[u];
        }
    }
}

Estruturas Cíclicas e Efeitos Posteriores

DP em Anéis

Problemas em estruturas circulares podem ser resolvidos transformando o ciclo em cadeia. Duas abordagens comuns são:

• Abrir o ciclo em um ponto arbitrário e executar duas DP: uma sem restrição e outra impondo uma condição de contorno (por exemplo, o primeiro e o último elementos não ambos escolhidos).
• Duplicar a cadeia e usar janela deslizante sobre [1..2N].

O uso de array circular de tamanho 2 otimiza o consumo de memória quando a transição depende apenas do estado imediatamente anterior.

Lidando com Efeitos Posteriores

Quando a transição natural apresenta dependência que viola a propriedade de ausência de efeito posterior, é comum redefinir o estado para absorver a informação problemática, tornando-a parte do próprio estado.

Técnicas de Otimização

Compressão de Estado

Conjuntos pequenos podem ser representados por máscaras de bits. Se há N elementos, cada subconjunto pode ser codificado por um inteiro entre 0 e 2^N - 1.

int n;
int distancia[MAX][MAX];
int memoViajem[1 << MAX][MAX];

int rec(int visitados, int atual) {
    if (memoViajem[visitados][atual] >= 0) return memoViajem[visitados][atual];
    if (visitados == (1 << n) - 1) return 0;

    int melhor = INF;
    for (int prox = 0; prox < n; prox++) {
        if (!(visitados >> prox & 1)) {
            melhor = min(melhor, rec(visitados | (1 << prox), prox) + distancia[atual][prox]);
        }
    }
    return memoViajem[visitados][atual] = melhor;
}

Outras Otimizações

• Binary lifting: acelera transições que dependem de potências de dois em estados.
• Estruturas de dados: árvores de segmentos e fenwick trees aceleram consultas em intervalos durante a transição.
• Fila monotônica: remove elementos obsoletos de janelas deslizantes, reduzindo a complexidade de O(n²) para O(n).
• Otimização por convex hull (slope trick): útil quando a transição envolve funções lineares por partes.
• Desigualdade quadrilateral: permite otimizar a escolha do ponto de divisão em DP de intervalos quando a função de custo satisfaz certas propriedades.