Published

22/04/2026

Modified

22/04/2026

Programação Dinâmica (Dynamic Programming - DP)

A Programação Dinâmica é um paradigma de projeto de algoritmos que se baseia em dividir um problema em subproblemas menores, resolvê-los uma única vez e armazenar seus resultados para evitar cálculos redundantes no futuro.

Geralmente, aplicamos Programação Dinâmica quando um problema possui duas propriedades intrínsecas:

  1. Subproblemas Sobrepostos (Overlapping Subproblems): O algoritmo divide o problema em subproblemas menores que são exigidos e solucionados repetidas vezes ao longo da execução.
  2. Subestrutura Ótima (Optimal Substructure): A solução ótima do problema principal pode ser construída combinando-se as soluções ótimas de cada um de seus subproblemas.

O Problema do Recálculo: Sequência de Fibonacci

Vimos na parte de funções que uma estratégia é adotar a recursividade. A relação de recorrência clássica para computar o \(n\)-ésimo número da sequência de Fibonacci é:

\[ \text{Fib}(n) = \text{Fib}(n-1) + \text{Fib}(n-2) \] Considerando os casos base \(\text{Fib}(0) = 0\) e \(\text{Fib}(1) = 1\).

Apesar de intuitiva, a implementação puramente recursiva é ineficiente. Veja a árvore de chamadas caso desejemos calcular o 5º número da sequência de Fibonacci (Fib(5)):

Atenção: Na árvore acima, o valor da chamada iterativa de Fib(2) é recalculado 3 vezes, Fib(3) é calculado 2 vezes, e assim por diante. O número de chamadas cresce exponencialmente. Para um problema um pouco maior (como Fib(50)), o tempo de execução no puramente recursivo já extrapola o tolerável. Sua complexidade nesse passo seria de \(O(2^n)\).

A Solução: Memorização (Top-Down)

Para evitar recálculos inúteis, podemos salvar (memorizar) os resultados já gerados, os resgatando da base de armazenamento (variável, array/vetor ou matriz) e devolvendo imediatamente caso requirido. O custo dessa ação se resume em \(O(1)\).

A isso também chamamos de Memoization (Memorização), a qual configura e caracteriza a abordagem Top-Down (De cima para baixo), onde começamos no problema original (topo) e vamos progressivamente partindo-o em problemas menores (para a base) pela via recursiva.

A estrutura ou bloco isolado na DP é comumente conhecido por estado. Em Fibonacci, o estado em trânsito é a própria configuração de posição e subnível de sua sequência (argumento iterado).

Confira logo em seguida essa concepção no C++. Observe também que adicionamos o <cassert> para criarmos mini-testes automatizados e demonstrarmos como checar a validade do algoritmo sem depender puramente do printf/cout.

#include <iostream>
#include <cstring>
#include <cassert> // Para aplicar os testes

#define MAXN 1000100

// Vetor que estoca os estados
int dp[MAXN];

int fib(int x) {
    // 1. Verificação primária: Já esbarrei na mesma resolução?
    if(dp[x] != -1) {
        return dp[x]; // Consome em puro O(1)
    }

    // 2. Condições base / de contorno
    if(x == 0) return 0;
    if(x == 1) return 1;

    // 3. Efetua a função de transição / recorrência associada
    // IMPORTANTE: salva no slot o valor obtido ANTES da devolução!
    dp[x] = fib(x-1) + fib(x-2);
    
    return dp[x];
}

void executando_testes() {
    // memset é função do <cstring> a qual limpa os bits na memória contígua e a injeta com o default
    // Aqui usamos o -1 como sentinela ("Ainda não há dado válido ou processado nesta posição")
    memset(dp, -1, sizeof(dp));

    // Validando asserções
    assert(fib(0) == 0);
    assert(fib(1) == 1);
    assert(fib(5) == 5);
    assert(fib(6) == 8);
    assert(fib(10) == 55);
    
    std::cout << "[✅] Testes efetuados para Top-Down (Memoization).\n";
}

int main() {
    executando_testes();
    return 0;
}

Visualmente, aquela nossa complexa árvore foi enxugada, onde ramificações inúteis (“galhos podados”) não serão invocados novamente. Analisando o funcionamento:

Concluímos portanto uma queda fenomenal de exigência operacional. Como cada chamada é tratada em um slot de arranjo uma única vez, a nova estimativa de limite em tempo passou a linear (\(O(n)\)).

Tabulação (Bottom-Up)

A Programação Dinâmica comporta outra solução arquitetural: podemos construir iterativamente começando justamente com as amostras de base prontas resolvendo até subirmos na abstração buscada. O fluxo invertido dá significado e o nome: Tabulação (Bottom-Up).

Na prática, geramos o armazenamento (Tabela/Vetor) e processamos num laço (for).

#include <iostream>
#include <cassert>

#define MAXN 1000100

int fib_bottom_up(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    int dp_tab[MAXN];
    
    // 1. Carregamos o alicerce estático base
    dp_tab[0] = 0;
    dp_tab[1] = 1;

    // 2. Transição natural da base -> nível macro
    for(int i = 2; i <= n; i++){
        dp_tab[i] = dp_tab[i-1] + dp_tab[i-2];
    }

    return dp_tab[n];
}

void executando_testes_btu() {
    // Validando asserções
    assert(fib_bottom_up(0) == 0);
    assert(fib_bottom_up(1) == 1);
    assert(fib_bottom_up(5) == 5);
    assert(fib_bottom_up(6) == 8);
    assert(fib_bottom_up(10) == 55);

    std::cout << "[✅] Testes efetuados para Bottom-Up (Tabulação).\n";
}

int main(){
    executando_testes_btu();
    return 0;
}

A complexidade é a mesma \(O(n)\).

Diferenciais Bottom-Up: A vantagem da vertente é imunidade aos transbordamentos das famosas pilhas de recursão nas arquiteturas subjacentes (os Stack Overflows). Como não há empilhamento vertical do contexto contínuo, a versão opera inteiramente atritada ao loop for/while enxuto. Contraponto é que iterativamente (para grande maioria dos casos de uso complexos), todo o plano (espaço matricial e todas subinstâncias de preenchimento) do limite precisará ser invariavelmente percorrido, enquanto as Top-Down operam sob demanda estrita e pontual.

Complexidade em Programação Dinâmica

A complexidade de tempo global numa problemática genérica pela técnica obedece uma forte regra estimada:

\[ \text{Complexidade de Tempo} = \text{Quantidade de Estados} \times \text{Tempo Investido na Transição (Gasto por Estado)} \]

No contexto supracitado de Fibonacci: - Quantidade de Estados: \(O(n)\) - Transição (Tempo de Cada Estado): \(O(1)\) (Uma mera soma entre dois adjacentes salvos) - Complexidade Total: \(O(n) \times O(1) = \mathbf{O(n)}\)

Outro Exemplo: Subindo Escadas (Climbing Stairs)

Imagine que você quer atingir o topo de uma grande escadaria composta por numeração de degraus de até \(n\). Em sua rotina ou preparo de impulso mecânico muscular é aceitável ultrapassar (dar grandes passadas duplas) se alternando ou em pares, sendo livre combinar qualquer progresso por 1 degrau ou alternativamente 2 de cada vez! Como poderíamos prever exaustivamente todas permutações sequenciais ou percursos formados para bater essa escalada partindo do degrau zero?

Mapeamento mental: Se quero pousar ou pisar o meu destino absoluto (no hipotético degrau i). 1. Qual passo dei por penúltimo, pra conseguir? Bem, se minha maior pernada final em salto é estrita a pular pro +2, no mínimo eu teria cravado piso no degrau anterior em i - 2 passos finalizando. 2. A outra resposta mais prudente é dar os corriqueiros normais, avançar pulo com perna simples de \(+1\), partindo então diretamente do degrau referenciado local i - 1.

Isso nos induz logicamente: as variantes de pisadas até chegado destino central (i) compõem o somatório dos próprios possíveis trechos do local logo em sua vizinhança inferior originados das matrizes anteriores imediatas do seu recuo.

Relação de Recorrência Transpassada / Condensada: \(\text{DP}(i) = \text{DP}(i - 1) + \text{DP}(i - 2)\).

(Conjecturou alguma intuição e intuição analítica forte disto? Reduzimos as chances a formulações universais idênticas do Fibonacci - um belo efeito cíclico do ramo acadêmico DP para resolver vertentes combinatórias diferentes das abstrações)

Codificação final para sedimentar testagem de software nas propostas:

#include <iostream>
#include <vector>
#include <cassert>

int subindo_escadas(int n) {
    if (n <= 1) return 1; // Base analítica pura
                          // (Ou pulei pro começo por 1, ou de 0 eu me mantenho nele também como 1 única tática)

    std::vector<int> dp(n + 1);
    dp[0] = 1;
    dp[1] = 1;
    
    // Bottom Up padrão no arranjo limitante n <= X
    for(int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}

void testar_climbing_stairs() {
    assert(subindo_escadas(2) == 2); // Explicito: 1+1 (sequência passadas curtas) OR 2 direto = Total 2
    assert(subindo_escadas(3) == 3); // Cenoáriário 3
    assert(subindo_escadas(4) == 5); 
    assert(subindo_escadas(5) == 8);

    std::cout << "[✅] Testes do cenário Escadaria Combinação foram completados sem erros!\n";
}

int main() {
    testar_climbing_stairs();
    return 0;
}

Exercícios Sugeridos

Não basta apenas entender as subestruturas sobrepostas nas teorias superficiais e abstratas para evoluir os modelos. Há grande vastidão que englobam tabulações matriciais bi ou multidimensionais em otimizações. Exercícios formam sua base intuitiva para identificá-los em campeonatos em frações de segundos:

Back to top