Recursão e programação dinâmica

Recursão

Uma função recursiva tem um caso base (a resposta direta, como fib(0) = 0 e fib(1) = 1) e um passo que chama a si mesma com uma entrada menor. Cada chamada ocupa um quadro na pilha: recursão muito profunda estoura a pilha — às vezes um laço é melhor.

Programação dinâmica

Quando os mesmos subproblemas se repetem e a resposta ótima se monta a partir das respostas ótimas dos menores, guarde-as. Duas formas:

• De cima para baixo (memoização): a recursão de sempre, com um mapa de respostas já calculadas.
• De baixo para cima (tabulação): um laço que preenche a tabela do menor para o maior, sem recursão.

Como reconhecer

Perguntas como "de quantas formas…", "qual o mínimo/máximo…" ou "é possível…" sobre sequências e escolhas costumam ser DP: troco com menos moedas, mochila, maior subsequência comum (o diff do Git), distância de edição (corretor ortográfico). Defina o estado, a transição e o caso base — o resto é preencher a tabela.

// O(2ⁿ): recalcula os mesmos valores milhões de vezes
func fib(_ n: Int) -> Int {
    n < 2 ? n : fib(n - 1) + fib(n - 2)
}

// O(n) de tempo, O(1) de espaço: tabulação guardando só os dois últimos
func fib(_ n: Int) -> Int {
    var (a, b) = (0, 1)
    for _ in 0..<n { (a, b) = (b, a + b) }
    return a
}

// Troco com menos moedas: menor[v] = 1 + min(menor[v - moeda])
func menosMoedas(_ valor: Int, _ moedas: [Int]) -> Int? {
    var menor = [0] + Array(repeating: Int.max, count: valor)
    for v in stride(from: 1, through: valor, by: 1) {
        for m in moedas where m <= v && menor[v - m] != Int.max {
            menor[v] = min(menor[v], menor[v - m] + 1)
        }
    }
    return menor[valor] == Int.max ? nil : menor[valor]
}