Memoização versus Tabulação
Conheça duas formas de armazenar respostas de subproblemas em cache.
Memoização versus Tabulação é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 1 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Competitive Programming Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Competitive Programming Academy inclui 4 aulas no total.
Por que armazenar resultados
A recursão ingênua refaz o mesmo trabalho repetidamente. A programação dinâmica armazena cada resposta uma vez, para que você nunca precise recalculá-la.
fib(40) # slow: recomputes endlesslySubproblemas sobrepostos
DP se aplica quando um problema se divide em subproblemas sobrepostos. O mesmo caso menor aparece em vários ramos da recursão.
fib(5) needs fib(3) twiceDe cima para baixo: memoização
Memoização é uma recursão comum acrescida de um armazenamento de resultados. Você calcula conforme necessário e guarda o resultado na primeira vez que encontra cada entrada.
memo = {}Memoização fácil em Python
O decorador lru_cache transforma uma recursão lenta em uma DP rápida com uma única linha, armazenando automaticamente o resultado de cada chamada.
from functools import lru_cache
@lru_cache(None)
def f(n): ...De baixo para cima: tabulação
A tabulação preenche uma tabela, começando pelos menores casos e avançando até a resposta, usando um laço em vez de recursão.
dp = [0] * (n + 1)Um Fibonacci tabulado
Defina os valores-base e depois faça cada célula ler os valores já calculados. Sem pilha de chamadas, apenas um laço organizado.
dp[0], dp[1] = 0, 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]Mesma resposta, estilo diferente
A memoização e a tabulação resolvem a mesma recorrência. Elas diferem apenas na direção: de cima para baixo, conforme necessário, ou de baixo para cima, em ordem.
Quando preferir a memoização
Prefira a memoização quando a recorrência for natural de escrever e talvez você não precise de todos os estados.
Quando preferir a tabulação
Escolha a tabulação para laços rápidos, para evitar erros de limite de recursão e quando você for calcular a tabela inteira de qualquer maneira.
import sys; sys.setrecursionlimit(10**6)Fique atento ao limite de recursão
Uma recursão memoizada profunda pode atingir o limite de recursão do Python e falhar com um veredito de erro em tempo de execução em entradas grandes.
Ambas compartilham um custo
De qualquer forma, o ganho de velocidade vem de resolver cada estado uma vez. O tempo total é o número de estados multiplicado pelo trabalho por estado.
Verificação rápida
Qual abordagem preenche uma tabela de baixo para cima usando um laço?
Revisão: dois caminhos, uma DP
Agora você pode armazenar subproblemas de duas maneiras. A memoização usa recursão de cima para baixo; a tabulação usa laços de baixo para cima. Escolha a que for mais clara de ler. ✨
Perguntas Frequentes
A aula “Memoização versus Tabulação” é grátis?
Sim — o texto completo de “Memoização versus Tabulação” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Competitive Programming Academy, atualize para CoddyKit PRO. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que vou aprender em “Memoização versus Tabulação”?
Conheça duas formas de armazenar respostas de subproblemas em cache. Você pratica Competitive Programming Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Competitive Programming Academy?
Nenhuma experiência prévia é necessária. Competitive Programming Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 1 de 4.
Quanto tempo leva a aula “Memoização versus Tabulação”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Competitive Programming Academy?
Sim. Cada aula de Competitive Programming Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Memoização versus Tabulação
- Defina o Estado e a Transição
- Subida de Escadas e Combinações de Moedas
- Maior Subsequência Crescente