Memoização: Armazenando Resultados Recursivos em Cache

O Fibonacci recursivo ingênuo calcula os mesmos valores repetidamente. fib(5) chama fib(4) e fib(3); fib(4) chama fib(3) e fib(2) — portanto, fib(3) é calculado duas vezes. Essa redundância cresce exponencialmente: fib(40) faz mais de um bilhão de chamadas de função. A memoização resolve isso armazenando cada resultado na primeira vez em que ele é calculado, para que as chamadas subsequentes o recuperem em O(1), em vez de recalculá-lo.

Adicione um dicionário memo como parâmetro (ou use um fechamento). Antes de calcular, verifique se a resposta já está em memo. Se estiver, retorne-a imediatamente. Caso contrário, calcule-a, armazene-a em memo e retorne-a. Agora, cada subproblema distinto é calculado exatamente uma vez, transformando O(2^n) em tempo O(n) e espaço O(n) para o dicionário memo, além de O(n) de espaço para a pilha.

Python fornece @functools.lru_cache(maxsize=None) (também disponível como @functools.cache no Python 3.9 ou posterior) para automatizar a memoização. Adicionar esse decorador acima de uma função armazena todas as chamadas com base em seus argumentos. maxsize=None significa que o tamanho do armazenamento temporário é ilimitado — cada combinação distinta de argumentos é armazenada. Isso transforma qualquer função recursiva em uma versão com memoização usando uma única linha de código.

LeetCode 70, 'Subida de Escadas': você pode subir 1 ou 2 degraus por vez. Quantas maneiras existem de chegar ao degrau n? Isso é Fibonacci disfarçado: ways(n) = ways(n-1) + ways(n-2). Casos-base: ways(0) = 1 (uma maneira de permanecer no chão), ways(1) = 1. Com memoização, o tempo é O(n) e o espaço é O(n).

LeetCode 322, 'Troco': dadas as denominações e um valor-alvo, encontre o número mínimo de moedas. Recursão de cima para baixo com memoização: dp(amount) = 1 + min(dp(amount - coin)) para cada moeda válida. O caso-base é: dp(0) = 0. Armazene temporariamente cada subvalor. Se um subvalor for impossível, retorne infinito. A memoização transforma a força bruta exponencial em tempo O(valor-alvo × quantidade de moedas).

LeetCode 139, 'Divisão de Palavras': determine se uma cadeia de caracteres pode ser segmentada em palavras do dicionário. A recursão de cima para baixo: can_break(s, start) tenta cada prefixo s[start:end]; se ele estiver no dicionário e can_break(s, end) for verdadeiro, retorne verdadeiro. Sem memoização, isso é O(2^n); com memoização (armazenando temporariamente cada índice inicial), torna-se O(n² × L), em que L é o comprimento máximo de uma palavra.

Memoização (de cima para baixo) começa com o problema original e armazena as respostas à medida que elas são descobertas recursivamente. Ela resolve apenas os subproblemas realmente necessários. A tabulação (de baixo para cima) preenche previamente uma tabela, partindo de subproblemas pequenos até chegar aos grandes, e resolve todos os subproblemas. A memoização é mais fácil de derivar de uma solução recursiva; a tabulação evita limitações de profundidade da recursão e a sobrecarga de chamadas de função.

Muitos problemas de DP que a recursão com memoização resolve usando espaço O(n) podem ser ainda mais otimizados para espaço O(1) quando apenas um número fixo de respostas de subproblemas anteriores é necessário. Para Fibonacci, somente os dois últimos valores importam. Para a subida de escadas, ocorre o mesmo. Duas variáveis deslizantes substituem todo o dicionário ou a tabela de memoização.

Há três maneiras de implementar a memoização manualmente. Um dicionário global é simples, mas polui o escopo do módulo. Um fechamento encapsula o armazenamento temporário dentro da função, evitando vazamentos, mas exige uma função envoltória. @lru_cache é a opção mais limpa — um único decorador substitui todo o código repetitivo. Em uma entrevista, comece com @lru_cache, a menos que o entrevistador peça especificamente uma implementação manual.

A memoização só acelera problemas com subproblemas sobrepostos — casos em que o mesmo subproblema é calculado várias vezes. Se cada subproblema for único (como em um percurso simples de árvore, em que cada nó é visitado exatamente uma vez), a memoização adicionará sobrecarga sem benefício. Além disso, a memoização não pode corrigir problemas em que a árvore recursiva é exponencial no número de subproblemas distintos, e não no reaproveitamento — esses problemas exigem um algoritmo completamente diferente.

Aplique a memoização quando: você tiver uma solução recursiva correta, mas lenta devido a recálculos redundantes; a função tiver um número pequeno de combinações distintas de argumentos; e o valor retornado depender apenas dos argumentos (função pura — sem efeitos colaterais e sem estado global). Verifique o espaço de estados dos subproblemas: se houver no máximo O(n) ou O(n²) estados distintos, a memoização transforma o tempo exponencial em polinomial.

Verifique sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.

Nesta lição, você aprendeu: a memoização armazena os resultados dos subproblemas para evitar recálculos, transformando a recursão exponencial em tempo polinomial, @functools.lru_cache é a ferramenta idiomática do Python e requer apenas uma linha e a memoização (de cima para baixo) e a tabulação (de baixo para cima) são os dois estilos de DP — a memoização é mais fácil de derivar, enquanto a tabulação evita problemas de profundidade da pilha. Parabéns — você concluiu os módulos de recursão e mapas de dispersão!