Uma escada tem n degraus. A cada passo você sobe 1 ou 2 degraus. De quantas formas
diferentes dá para chegar ao topo? A ordem dos passos importa: 1+2 e 2+1 são formas diferentes.
n = 3 → 3
1+1+1, 1+2 e 2+1.
n = 5 → 8
É o exemplo animado abaixo. Sem DP, a recursão ingênua faria 15 chamadas; com n = 40, mais de 300 milhões.
Restrições: 1 ≤ n ≤ 45
Tabulation: dp[i] = jeitos de chegar ao degrau i. O último passo até
i saiu do degrau i-1 (passo de 1) ou do i-2 (passo de 2), então
dp[i] = dp[i-1] + dp[i-2]. É a sequência de Fibonacci disfarçada: 1, 1, 2, 3, 5, 8...
Um laço de 2 até n; o array guarda os n + 1 degraus.
n + 1 células. Repare que cada dp[i] só é lido nas duas rodadas seguintes: depois disso ele é peso morto.
No array, dp[i] só lê dp[i-1] e dp[i-2]. Tudo antes disso
nunca mais é usado. Então basta guardar os dois últimos valores: a (degrau i-2) e
b (degrau i-1). A cada rodada a janela anda um degrau e o valor mais velho é sobrescrito. Memória
O(1), qualquer que seja n.
Mesmo laço, mas só a, b e c ficam na memória: 3 células para qualquer n.
Três células (12 B) para qualquer n, contra n + 1 do array.
Memoization (top-down): f(i) = jeitos de chegar ao degrau i, calculado como
f(i-1) + f(i-2). Sem memo, a recursão vira uma árvore binária com O(2ⁿ) chamadas,
porque f(3) é pedido por f(5) e por f(4), f(2) mais vezes ainda... Com
memo, cada f(i) é calculado uma vez e o resto vira cache hit: O(n).
Cada f(i) é calculado uma vez (sem memo seria O(2ⁿ)). O memo tem n + 1 células e a call stack chega a n frames.
memo[0] e memo[1] nunca são gravados: o caso base devolve 1 direto. A stack chega a n frames.