Dynamic Programming (DP) - Programação Dinâmica
O que é DP? A Ideia Central
DP resolve problemas complexos dividindo-os em subproblemas menores e guardando os resultados para não recalcular.
DP: APRENDENDO COM A HISTÓRIA
Imagine que você está calculando quanto tempo para chegar ao trabalho:
Você não vai recalcular o tempo de "Casa para Metrô" toda vez, né?
Você guarda esse tempo na memória!
DP funciona igual:
• Divide o problema grande em partes menores
• Resolve cada parte uma vez
• Guarda o resultado (memoização)
• Usa os resultados guardados para resolver o problema maior
Framework para DP: Os 4 Passos
PASSO 1: IDENTIFICAR A ESTRUTURA OTIMAL • Pergunte: "Qual é a melhor solução para este subproblema?" PASSO 2: DEFINIR O ESTADO • O que você PRECISA SABER para resolver o problema? • Exemplos: • dp[i] = valor máximo usando elementos 0...i • dp[i][j] = custo mínimo para transformar s[0:i] em t[0:j] PASSO 3: DEFINIR A TRANSIÇÃO • Como você chega ao estado atual a partir dos estados anteriores? • dp[i] = max(dp[i-1], dp[i-2] + valor[i]) ← escolha a melhor! PASSO 4: DEFINIR OS CASOS BASE • Quais são os menores subproblemas que você conhece a resposta? • dp[0] = valor_base • dp[1] = valor_para_um_elemento
Memoization vs Tabulation
Top-down (Memoization): Recursivo + cache. Mais natural para problemas complexos.
def fib_memo(n, memo={}):
if n in memo: return memo[n]
if n <= 1: return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]
# fib(5) = fib(4) + fib(3)
# = (fib(3)+fib(2)) + (fib(2)+fib(1))
# = ((fib(2)+fib(1))+(fib(1)+fib(0))) + ...
#
# Sem memo: O(2^n) - exponencial!
# Com memo: O(n) - cada fib calculado só 1 vez!
Bottom-up (Tabulation): Iterativo preenchendo a tabela. Mais memória eficiente.
def fib_tab(n):
if n <= 1: return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
# Preenche dp[0], dp[1], dp[2], ... dp[n]
# Sem recursão → sem stack overflow!
Space Optimization
Muitos DPs usam apenas os estados anteriores:
# Fibonacci padrão: O(n) espaço
dp = [0] * (n + 1)
# Fibonacci otimizado: O(1) espaço!
def fib_optimized(n):
if n <= 1: return n
prev2, prev1 = 0, 1
for _ in range(2, n + 1):
curr = prev1 + prev2
prev2 = prev1
prev1 = curr
return prev1
# dp[i-1] e dp[i-2] são os únicos estados necessários!
# Para Edit Distance (2D → 1D):
# dp[j] representa dp[i-1][j] do quadro anterior
# dp[j-1] representa dp[i][j-1] do quadro atual
DP vs Recursão Bruta
DP evita trabalho redundante ao guardar resultados:
# Recursão ingênua para Fibonacci(20):
# Chamadas: fib(20), fib(19), fib(18), fib(17), ...
# fib(18) é calculado 2x, fib(17) 3x, fib(16) 5x...
# Total: ~10,000 chamadas!
# Com memoização:
# fib(20), fib(19), fib(18), ... fib(0)
# Total: 21 chamadas apenas! 400x menos!
Árvore de chamadas (sem memo):
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \
fib(2) fib(1)
↑ fib(2) calculado 3x, fib(1) calculado 2x!
Quando usar DP:
Problemas de otimização, subproblemas sobrepostos, escolha entre opções, longest common/increasing subsequences, fibonacci-like patterns.
Tipos de DP:
- 1D: Fibonacci, House Robber, Climbing Stairs
- 2D: Unique Paths, Edit Distance, Longest Common Subseq
- Space optimization:
Problemas Essenciais - 1D DP
Longest Increasing Subsequence
Medium
Encontre o comprimento da maior subsequência crescente.
Resolver no LeetCode →Problemas Essenciais - 2D DP
Graph Algorithms
Dijkstra's Algorithm (MUITOO importante para Uber):
Encontrar caminho mais curto em grafos com pesos positivos.
import heapq
def dijkstra(graph, start):
dist = {node: inf for node in graph}
dist[start] = 0
pq = [(0, start)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]: continue
for v, w in graph[u]:
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
heapq.heappush(pq, (dist[v], v))
def dijkstra(graph, start):
dist = {node: inf for node in graph}
dist[start] = 0
pq = [(0, start)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]: continue
for v, w in graph[u]:
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
heapq.heappush(pq, (dist[v], v))
Por Que O(E log V)?
Complexidade vem do heap usado para encontrar o próximo nó mais perto:
Dijkstra com E=1000 arestas, V=100 nós: Para cada nó processado (V vezes): 1. Extrair mínimo do heap: O(log V) ← heap pop 2. Para cada aresta do nó: relaxamento O(1) + possivelmente heap push O(log V) Total: • V heap pops → O(V log V) • E heap pushes (máximo) → O(E log V) Resultado: O((V + E) log V) = O(E log V) para grafos esparsos! vs. Sem heap (array): • Encontrar mínimo: O(V) → Total O(V²) • Para V=100, E=1000: V²=10.000 vs E log V=10.000 (mesmo!) • Para V=10.000, E=100.000: V²=100.000.000 vs E log V=1.600.000 → 60x mais rápido!
Por Que Não Funciona com Pesos Negativos?
Pesos negativos podem criar ciclos que diminuem a distância indefinidamente:
A --2--> B
↑ |
| -5
Caminho: A → B → A → B → A → B → ...
Distância total: 2 + (-5) + 2 + (-5) + ... → -∞
Dijkstra assume que depois de processar um nó,
não existe caminho mais curto para ele.
(Isto é violado com pesos negativos!)
Solução: Bellman-Ford (O(VE)) para grafos com pesos negativos.
Union Find:
Detectar componentes conectados, cycle detection em grafos.
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px == py: return False
parent[px] = py
return True
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px == py: return False
parent[px] = py
return True
Problemas Essenciais - Dijkstra
Find the City With Smallest Number
Medium
Cidade com menor número de reachable nodes.
Resolver no LeetCode →Problemas Essenciais - Union Find
Binary Search (Busca Binária)
O que é Binary Search? A Ideia Central
Binary Search encontra um elemento em um array ordenado dividindo o espaço de busca pela metade a cada passo.
ADIVINHE O NÚMERO DE 1 A 100!
"50!" → "Muito alto!" → elimina 51-100 (50 números de uma vez!)
"25!" → "Muito baixo!" → elimina 1-25 (25 números de uma vez!)
"37!" → "Muito alto!" → elimina 38-50
"31!" → "Correto!"
Você acertou em 4 tentativas! vs. 100 tentativas (linear)!
log₂(100) ≈ 7 → Binary search é MAGIC!
Por Que O(log n)? Cada Passo Elimina Metade!
1.000.000 DE ELEMENTOS:
1.000.000 → 500.000 → 250.000 → 125.000 → 62.500 → ... → 1
↓ ↓ ↓ ↓ ↓ ↓ ↓
iteração 1 iteração 2 iteração 3 iteração 4 iteração 5 ...
Total: ~20 iterações!
vs. Linear search: 1.000.000 comparações!
SPEEDUP: 50.000x!
log₂(n) = quantas vezes dividir n por 2 até 1
log₂(1M) ≈ 20 | log₂(1B) ≈ 30
Template Completo
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right: # <= é importante!
mid = left + (right - left) // 2 # Evita overflow
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# Por que left + (right - left) // 2?
# left + right pode overflow em linguagens com tamanho fixo!
Variações Importantes
1. LOWER BOUND: Primeira posição >= target
def lower_bound(arr, target):
left, right = 0, len(arr)
while left < right:
mid = left + (right - left) // 2
if arr[mid] < target:
left = mid + 1
else:
right = mid
return left
2. UPPER BOUND: Primeira posição > target
def upper_bound(arr, target):
left, right = 0, len(arr)
while left < right:
mid = left + (right - left) // 2
if arr[mid] <= target:
left = mid + 1
else:
right = mid
return left
3. BINARY SEARCH ON ANSWER: Encontrar resposta (não índice)
def min_speed(packets, days):
low, high = max(packets), sum(packets)
while low < high:
mid = (low + high) // 2
if can_deliver(mid, days):
high = mid # Funciona, tenta menor
else:
low = mid + 1 # Não funciona, precisa maior
return low
Problemas Essenciais
Median of Two Sorted Arrays
Hard
Mediana de dois arrays ordenados em O(log(n+m)).
Resolver no LeetCode →
Capacity to Ship Packages
Medium
Capacidade mínima para enviar todos os pacotes em D dias.
Resolver no LeetCode →Trie (Prefix Tree)
Quando usar Trie:
Autocomplete, prefix matching, longest prefix match, word search, dictionary, IP routing (trie de rotas).
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True
Casos de Uso Reais:
- Search engines - autocomplete
- DNS routing - longest prefix match
- T9 texting - predictive text
- Spell checker - validar palavras
Problemas Essenciais
Heap / Priority Queue (Filas de Prioridade)
O que é Heap? A Ideia Central
Heap é uma estrutura de dados que sempre mantém o maior (max-heap) ou menor (min-heap) elemento no topo.
HEAP: SEMPRE O MAIOR (OU MENOR) NO TOPE!
Max-Heap: 50
/ \
30 20
/ \ / \
10 15 5 8
Operações:
• Insert: O(log n) - adiciona e rearranja
• Get max: O(1) - o topo é sempre o maior!
• Extract max: O(log n) - remove e rearranja
Aplicações:
• Priority queue (printers, CPU scheduling)
• Top K elementos
• Median de stream
• Dijkstra (sempre pegar o nó mais próximo)
Como o Heap Funciona: Árvore → Array
HEAP É UMA ÁRVORE BINÁRIA COMPLETA!
Árvore: Array:
50 [50, 30, 20, 10, 15, 5, 8]
/ \ [0] [1] [2] [3] [4] [5] [6]
30 20
/ \ / \
10 15 5 8
RELAÇÕES NO ARRAY:
• Parent de i = (i - 1) // 2
• Filho esquerdo = 2 * i + 1
• Filho direito = 2 * i + 2
Exemplo: elemento no índice 3
• Parent: (3 - 1) // 2 = 1 → arr[1] = 30
Por Que O(log n)? A Altura da Árvore
HEAP COM ALTURA LOG(N)!
Nível 0: 1 elemento (raiz)
Nível 1: 2 elementos
Nível 2: 4 elementos
...
Nível h: 2^h elementos
Total: 2^(h+1) - 1 ≈ 2^(h+1)
Se n = 2^(h+1): h = log₂(n)
Para 1.000.000 elementos:
Altura ≈ log₂(1.000.000) ≈ 20
Insert: sobe no máximo 20 níveis → O(log n)
Delete: desce no máximo 20 níveis → O(log n)
HEAP COMBINA O MELHOR:
• Array não ordenado: Insert O(1), Delete min O(n)
• Array ordenado: Insert O(n), Delete min O(1)
• HEAP: Insert O(log n), Delete min O(log n), Peek O(1)!
Onde Heap É Usado na Indústria
- CPU Scheduling: Processo com maior prioridade executa primeiro
- Uber: Match de motoristas mais próximos
- Mediana Online: Max-heap + min-heap
- Dijkstra: Sempre pegar nó com menor distância
Heapify: Construir Heap em O(n)
Para construir um heap de um array arbitrário:
# naive: insert n elementos = O(n log n)
for x in arr:
heapq.heappush(heap, x) # O(n log n)
# heapify: O(n) — muito mais rápido!
heapq.heapify(arr) # O(n)
# Por que O(n)?
# Leaf nodes (n/2) não precisam de ajuste
# Nodes na profundidade d tem n/2^(d+1) elementos
# Soma: n/2 + n/4 + n/8 + ... = n/2 * (1 + 1/2 + 1/4 + ...) = n
Casos de Uso Reais:
- Top stories - HN, Reddit ranking
- Mediana de dados - running median
- Merge K sorted - combine dados ordenados
- Dijkstra - otimizar extração do mínimo