O Próximo Nível: Uma Introdução à Programação Dinâmica (DP)

Receita 1: Memoização (Top-Down) - A Preguiça Inteligente

Você mantém a estrutura recursiva original, mas adiciona um "cache" (um mapa ou array) para guardar os resultados. Antes de fazer qualquer cálculo, você verifica se o resultado já está no cache.

Analogia: É como anotar o resultado de uma conta difícil em um post-it. Se precisar da mesma conta depois, você só olha o post-it.

// Passando o cache como parâmetro (mais robusto para testes)
function fibMemo(n, cache = {}) {
  // Se o resultado já está no cache, retorna ele em O(1).
  if (n in cache) {
    return cache[n];
  }

  // Caso Base
  if (n <= 1) {
    return n;
  }

  // Se não está no cache, calcula e GUARDA ANTES de retornar.
  // Passamos o cache nas chamadas recursivas.
  cache[n] = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
  return cache[n];
}
// Complexidade de Tempo: O(n) - Linear!
// Complexidade de Espaço: O(n) - para o cache.

Receita 2: Tabulação (Bottom-Up) - Construindo a Solução

Você resolve o problema de forma iterativa, "de baixo para cima". Você cria uma tabela (geralmente um array) e a preenche desde os casos base até a solução final.

Analogia: É como construir um muro. Você não começa pelo topo; você assenta os tijolos da base primeiro e vai subindo, camada por camada.

function fibTab(n) {
  if (n <= 1) return n;

  // 1. Cria uma "tabela" (array) para guardar os resultados.
  const table = Array(n + 1).fill(0);

  // 2. Preenche os casos base.
  table[1] = 1;

  // 3. Itera do começo até o fim, construindo a solução.
  for (let i = 2; i <= n; i++) {
    table[i] = table[i - 1] + table[i - 2];
  }

  // 4. O resultado final está na última posição da tabela.
  return table[n];
}
// Complexidade de Tempo: O(n) - Linear!
// Complexidade de Espaço: O(n) - para a tabela.

Refinamento da Tabulação: Otimizando para Espaço O(1)

Note que para calcular table[i], nós só precisamos dos dois valores anteriores (table[i-1] e table[i-2]). Não precisamos guardar a tabela inteira! Podemos otimizar o espaço usando apenas duas variáveis.

function fibTabOptimized(n) {
  if (n <= 1) return n;

  let a = 0; // Representa fib(i-2)
  let b = 1; // Representa fib(i-1)
  let c;     // Representa fib(i)

  for (let i = 2; i <= n; i++) {
    c = a + b;
    a = b;
    b = c;
  }

  return b;
}
// Complexidade de Tempo: O(n)
// Complexidade de Espaço: O(1) - UAU!

DP na Prática: O Problema da Escada (Climbing Stairs)

O Problema: Você está subindo uma escada com n degraus. A cada passo, você pode subir 1 ou 2 degraus. De quantas maneiras distintas você pode chegar ao topo?

Análise: Para chegar no degrau n, você só pode ter vindo do degrau n-1 (e dado um passo) ou do degrau n-2 (e dado dois passos). Portanto, maneiras(n) = maneiras(n-1) + maneiras(n-2). Opa! Isso é exatamente a relação de recorrência de Fibonacci!

function climbStairs(n) {
  // Casos base:
  // Se n=1, há 1 maneira (1 passo)
  // Se n=2, há 2 maneiras (1+1 ou 2)
  if (n <= 2) return n;

  // Começamos a iterar a partir de n=3.
  // "oneStepBefore" guarda as maneiras de chegar em n-1 (que é 2 para n=3)
  // "twoStepsBefore" guarda as maneiras de chegar em n-2 (que é 1 para n=3)
  let oneStepBefore = 2; // maneiras(2)
  let twoStepsBefore = 1; // maneiras(1)
  let allWays = 0;

  for (let i = 3; i <= n; i++) {
    allWays = oneStepBefore + twoStepsBefore;
    twoStepsBefore = oneStepBefore;
    oneStepBefore = allWays;
  }
  return allWays;
}