Reaproveite respostas com programação dinâmica
Divida os problemas em subproblemas sobrepostos e resolva cada um uma única vez.
- Reconhecer subproblemas sobrepostos.
- Escrever soluções com memoização (top-down) e com tabulação (bottom-up).
- Definir um estado de PD e uma recorrência.
A programação dinâmica (PD) se aplica quando um problema pode ser montado a partir das respostas de versões menores dele mesmo, e essas versões menores se repetem. A recursão simples as recalcula um número exponencial de vezes; a PD guarda cada resposta uma vez. Sinais típicos: “de quantas formas”, “custo mínimo”, “valor máximo”, “é possível” - sobre sequências, grades ou quantias.
Quatro passos até uma solução de PD
- Defina o estado: o que
dp[i]significa? Por exemplo, “o menor número de moedas que formam a quantia i”. - Escreva a recorrência: como
dp[i]depende de estados menores?dp[i] = 1 + min(dp[i - coin])sobre todas as moedas. - Defina os casos base:
dp[0] = 0. - Escolha uma ordem: preencha a tabela de modo que as dependências de cada estado estejam prontas (bottom-up), ou faça a recursão com um cache (memoização top-down).
1from functools import lru_cache
2
3@lru_cache(maxsize=None)
4def ways_to_climb(n):
5 # ways to reach step n taking 1 or 2 steps at a time
6 if n <= 1:
7 return 1
8 return ways_to_climb(n - 1) + ways_to_climb(n - 2)
9
10print(ways_to_climb(5), ways_to_climb(30))8 1346269
Sem o cache, ways_to_climb(30) faz mais de um milhão de chamadas; com ele, só 31. A tabulação bottom-up calcula os mesmos valores num laço e muitas vezes permite guardar só as últimas entradas - aqui, duas variáveis - para ter espaço O(1). Sempre diga a complexidade como (número de estados) × (trabalho por estado).
Principais conclusões
PD = recursão + lembrar as respostas de subproblemas repetidos.
Defina o estado, a recorrência, os casos base e a ordem de cálculo.
A complexidade é mais ou menos estados × trabalho por estado.
Quiz da aula
5 perguntas · aprovação com 4 acertos · até 50 XP
Ao passar, você conclui a aula e mantém sua sequência. As perguntas erradas voltarão em sessões de revisão.
Pratique: resolva problemas de entrevistas técnicas
Resolva um problema clássico de entrevista em Python e execute-o com casos de teste. Busque a complexidade ideal e depois confira os casos extremos. Os exercícios rodam localmente no navegador.
Dê troco com o menor número de moedas
Leia uma quantia e depois uma linha com os valores das moedas. Imprima o menor número de moedas necessário para formar exatamente a quantia (com moedas ilimitadas de cada tipo), ou -1 se for impossível.
- Moedas padrão
- A escolha gulosa falha
- Impossível
- Quantia zero
O Python é executado em um ambiente isolado no navegador, com limite de 60 segundos. O runtime é carregado pelo CDN do Pyodide; seu código permanece neste navegador.
Dúvidas sobre esta lição
Travou em algum ponto? Pergunte. Descobriu algo? Compartilhe. Explicar também é uma ótima forma de aprender.
Carregando publicações…