Algoritmos Avançados

A ideia central da Programação Dinâmica (DP) é simples: se a recursão calcula a mesma coisa várias vezes, guarde o resultado e reuse. Esse "guardar" se chama memoização.

O exemplo clássico — Fibonacci

Fibonacci é a sequência 1, 1, 2, 3, 5, 8, 13, 21... onde cada número é a soma dos dois anteriores. A definição recursiva é direta:

// Fibonacci ingênuo — O(2ⁿ)
public int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

O problema: fib(5) chama fib(4) e fib(3). fib(4) chama fib(3) e fib(2). fib(3) aparece duas vezes. fib(2) aparece três vezes. Em fib(50), são bilhões de chamadas redundantes.

Solução com memoização:

// Fibonacci memoizado — O(n)
private Map<Integer, Integer> cache = new HashMap<>();

public int fib(int n) {
    if (n <= 1) return n;
    if (cache.containsKey(n)) return cache.get(n);

    int resultado = fib(n - 1) + fib(n - 2);
    cache.put(n, resultado);
    return resultado;
}

Cada fib(n) é calculado uma vez só. fib(50) que demorava minutos passa a rodar em microssegundos.

Top-down vs Bottom-up

// Bottom-up — sem recursão, sem cache, só array
public int fib(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

Outros problemas clássicos de DP

• Problema do troco — qual a quantidade mínima de moedas pra dar X de troco?
• Mochila (Knapsack) — dado um peso máximo e itens com peso/valor, qual a melhor combinação?
• Subsequência comum mais longa (LCS) — usado em diff, controle de versão.
• Distância de edição (Levenshtein) — quantas operações pra transformar uma string em outra. Usado em corretor ortográfico.

Um algoritmo guloso (greedy) faz a escolha que parece melhor agora, sem se preocupar com o futuro. Nunca volta atrás. É rápido e simples — quando funciona.

Exemplo — problema do troco

Você precisa dar R$ 0,67 de troco com moedas de 50, 25, 10, 5 e 1 centavo. A estratégia gulosa: pega a maior moeda que cabe, repete.

public List<Integer> troco(int valor, int[] moedas) {
    Arrays.sort(moedas);  // ordem crescente
    List<Integer> resultado = new ArrayList<>();

    for (int i = moedas.length - 1; i >= 0; i--) {
        while (valor >= moedas[i]) {
            resultado.add(moedas[i]);
            valor -= moedas[i];
        }
    }
    return resultado;
}

Pra 67: pega 50 (sobra 17), pega 10 (sobra 7), pega 5 (sobra 2), pega 1 + 1 (sobra 0). Resultado: [50, 10, 5, 1, 1]. Cinco moedas. Ótimo.

Quando greedy falha

Imagina um sistema com moedas [1, 3, 4] e você precisa dar troco de 6. O greedy pega 4 + 1 + 1 = 3 moedas. Mas a solução ótima é 3 + 3 = 2 moedas. Greedy errou porque pegar 4 primeiro foi a melhor escolha local, mas não a melhor global.

Greedy só funciona quando o problema tem a propriedade da escolha gulosa ótima — ou seja, fazer a melhor escolha local realmente leva à melhor solução global. Provar isso é matemática, não intuição.

Algoritmos gulosos famosos

Backtracking é busca exaustiva organizada: tenta uma decisão, segue em frente, e se chegar num beco sem saída volta um passo (backtrack) e tenta outra. É como navegar um labirinto marcando o caminho com giz e voltando quando bate em parede.

O exemplo clássico — 8 rainhas

Coloque 8 rainhas num tabuleiro 8×8 sem que nenhuma ataque outra (nenhuma na mesma linha, coluna ou diagonal). Existem 92 soluções distintas.

Força bruta tentaria todas as 64!/(64-8)! ≈ 178 bilhões de posições. Backtracking corta drasticamente: coloca uma rainha por linha, e aborta assim que detecta conflito — nunca exploramos posições derivadas de uma escolha já inválida.

public boolean resolver(int[] tabuleiro, int linha) {
    if (linha == 8) return true;  // todas colocadas

    for (int col = 0; col < 8; col++) {
        if (seguro(tabuleiro, linha, col)) {
            tabuleiro[linha] = col;       // tenta
            if (resolver(tabuleiro, linha + 1)) {
                return true;
            }
            // backtrack — tenta a próxima coluna
        }
    }
    return false;  // nenhuma coluna funcionou
}

A árvore de decisão

Backtracking explora uma árvore implícita de decisões. Cada nó é uma escolha parcial. Folhas são soluções completas (ou becos sem saída). A poda corta sub-árvores inteiras quando você detecta que não levam a lugar nenhum.

Quanto mais cedo você detectar o beco, mais ramos você poda — e maior a economia. Detectar tarde = backtracking vira força bruta disfarçada.

Onde aparece

• Sudoku — testa números numa célula vazia, segue em frente, volta se travar
• Labirinto — explora caminhos, marca becos, retorna
• Permutações e combinações — gera todas as ordens possíveis
• Parser de expressões — testa interpretações alternativas
• Resolver Captchas / IA simbólica — busca em árvore com poda

Reconhecer o tipo de problema é o pulo do gato. Algumas perguntas pra fazer ao analisar:

Comparação direta

Combinar técnicas

Muito problema real combina mais de uma. Dijkstra é guloso mas usa fila de prioridade (heap, uma estrutura de dado eficiente). Branch-and-bound é backtracking + poda gulosa. Compiladores usam DP pra otimização e backtracking pra parsing. As técnicas são blocos de construção, não escolhas mutuamente exclusivas.