House Robber: Recorrência Escolher ou Ignorar
Modele a decisão de roubar ou ignorar como uma recorrência de DP, reduza o espaço a duas variáveis e estenda a solução para casas dispostas em círculo.
House Robber: Recorrência Escolher ou Ignorar é uma aula grátis de Coding Interview Prep 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 Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
O Problema do Ladrão de Casas
O problema do Ladrão de Casas pergunta: dado um vetor de inteiros não negativos que representa a quantia de dinheiro em cada casa, encontre a quantia máxima que você pode roubar sem roubar duas casas adjacentes. Por exemplo, [2, 7, 9, 3, 1] resulta em 12 (roubando as casas 0, 2 e 4). Esse é um problema clássico de DP 1D em que você toma uma decisão binária a cada etapa.
nums = [2, 7, 9, 3, 1]
# Can't rob adjacent houses
# Options: rob index 0 and 2 and 4 → 2+9+1=12
# or rob index 1 and 3 → 7+3=10
print('Max profit:', 12) # answer is 12Definindo a Recorrência
Considere dp[i] como o máximo de dinheiro roubado das primeiras i+1 casas. Em cada casa i, você tem duas opções: ignorá-la (usar dp[i-1]) ou roubá-la (usar nums[i] + dp[i-2]). A recorrência é dp[i] = max(dp[i-1], nums[i] + dp[i-2]). Esse é o padrão fundamental de escolher ou ignorar, que aparece em muitos problemas de DP.
# Recurrence: dp[i] = max(dp[i-1], nums[i] + dp[i-2])
# Base cases:
# dp[0] = nums[0] (only one house, rob it)
# dp[1] = max(nums[0], nums[1]) (take the richer of the two)
def rob(nums):
n = len(nums)
if n == 1: return nums[0]
dp = [0] * n
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i] = max(dp[i-1], nums[i] + dp[i-2])
return dp[-1]
print(rob([2, 7, 9, 3, 1])) # 12Percorrendo a Tabela de DP
Para [2, 7, 9, 3, 1], vamos percorrer a tabela: dp[0] = 2, dp[1] = max(2, 7) = 7, dp[2] = max(7, 9+2) = 11, dp[3] = max(11, 3+7) = 11, dp[4] = max(11, 1+11) = 12. A resposta final é dp[4] = 12. Percorrer a tabela manualmente confirma que a recorrência lida corretamente com as opções de escolher e ignorar em cada posição.
nums = [2, 7, 9, 3, 1]
dp = [0] * len(nums)
dp[0] = 2
dp[1] = max(2, 7) # 7
for i in range(2, len(nums)):
skip = dp[i-1]
take = nums[i] + dp[i-2]
dp[i] = max(skip, take)
print(f'dp[{i}] = max({skip}, {nums[i]}+{dp[i-2]}) = {dp[i]}')
print('Answer:', dp[-1])Reduzindo o Espaço para O(1)
A tabela de DP sempre consulta apenas as duas posições anteriores, portanto podemos substituir a matriz inteira por duas variáveis: prev2 (duas posições atrás) e prev1 (uma posição atrás). Após cada iteração, fazemos o deslocamento: prev2 = prev1 e prev1 = current. Isso reduz a memória de O(n) para O(1), mantendo a complexidade de tempo em O(n).
def rob_optimised(nums):
if not nums: return 0
if len(nums) == 1: return nums[0]
prev2 = nums[0]
prev1 = max(nums[0], nums[1])
for i in range(2, len(nums)):
curr = max(prev1, nums[i] + prev2)
prev2 = prev1
prev1 = curr
return prev1
print(rob_optimised([2, 7, 9, 3, 1])) # 12
print(rob_optimised([1, 2, 3, 1])) # 4Casos Extremos a Considerar
Sempre teste sua solução com casos extremos: um vetor vazio (retorne 0), um vetor com um único elemento (retorne esse elemento) e um vetor com dois elementos (retorne o maior dos dois). Em entrevistas, mencionar e tratar esses casos demonstra meticulosidade. A condição if n == 1 evita o acesso a um índice fora dos limites ao acessar nums[1] para dp[1].
def rob(nums):
if not nums: return 0
if len(nums) == 1: return nums[0]
prev2 = nums[0]
prev1 = max(nums[0], nums[1])
for i in range(2, len(nums)):
curr = max(prev1, nums[i] + prev2)
prev2, prev1 = prev1, curr
return prev1
print(rob([])) # 0
print(rob([5])) # 5
print(rob([3, 10])) # 10
print(rob([10, 3])) # 10Ladrão de Casas II: Casas em Círculo
A variante circular (LeetCode 213) coloca as casas em um círculo, fazendo com que a primeira e a última casa sejam adjacentes. Não é possível aplicar diretamente a recorrência linear. A ideia principal é: ou você rouba a primeira casa e exclui a última, ou exclui a primeira e inclui a última. Execute o ladrão de casas linear nos dois subvetores e escolha o maior valor.
def rob_linear(nums):
prev2, prev1 = 0, 0
for n in nums:
prev2, prev1 = prev1, max(prev1, n + prev2)
return prev1
def rob_circular(nums):
if len(nums) == 1: return nums[0]
# Either include first (exclude last) or include last (exclude first)
return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))
print(rob_circular([2, 3, 2])) # 3
print(rob_circular([1, 2, 3, 1])) # 4Por que a Abordagem Gulosa Falha Aqui
Uma abordagem gulosa ingênua poderia tentar sempre roubar a maior casa disponível. No entanto, isso falha em entradas como [2, 1, 1, 2]: a abordagem gulosa escolhe a casa 0 (valor 2) e depois a casa 3 (valor 2), totalizando 4, mas roubar as casas 0 e 2 também resulta em 3. Espere — neste caso, a abordagem gulosa funciona! Porém, tente [1, 3, 1, 3, 100]: a abordagem gulosa escolhe 3 e 3 (índices 1 e 3), totalizando 6, e perde a solução ideal 1+1+100=102. A DP é necessária porque escolhas localmente ideais não garantem um ótimo global.
# Greedy failure example
nums = [1, 3, 1, 3, 100]
# Greedy: pick max each step
# picks 3 (index 1), then 3 (index 3) → total 6
# DP optimal: pick 1 (index 0) + 1 (index 2) + 100 (index 4) → 102
def rob(nums):
prev2, prev1 = 0, 0
for n in nums:
prev2, prev1 = prev1, max(prev1, n + prev2)
return prev1
print(rob(nums)) # 102Reconhecendo o Padrão de Escolher ou Ignorar
O padrão de escolher ou ignorar se generaliza para além do ladrão de casas. Sempre que você percorre um vetor e, em cada posição, escolhe entre incluir o elemento atual (e ignorar o anterior) ou excluí-lo (e manter o resultado anterior), você tem uma DP de escolher ou ignorar. Procure restrições como não haver dois elementos adjacentes ou não haver intervalos sobrepostos como sinais para aplicar esse padrão.
# General take-or-skip template
def take_or_skip(values, gap=1):
'''Max sum where selected elements must be at least gap+1 apart.'''
n = len(values)
if n == 0: return 0
# dp[i] = best up to index i
dp = [0] * (n + gap)
for i in range(n):
take = values[i] + (dp[i - 1] if i >= 1 else 0)
skip = dp[i + gap - 1] if i + gap - 1 < len(dp) else 0
dp[i + gap] = max(skip, take)
return dp[-1]
print(take_or_skip([2, 7, 9, 3, 1])) # house robber-likeVariante Excluir e Ganhar
Excluir e Ganhar (LeetCode 740) pergunta: para cada número escolhido, você ganha num × count(num), mas deve excluir todas as ocorrências de num-1 e num+1. Isso se reduz diretamente ao ladrão de casas: construa um vetor earn[v] = v × count(v) para todos os valores e depois execute o ladrão de casas nesse vetor. Reconhecer reduções é uma habilidade importante em entrevistas.
from collections import Counter
def delete_and_earn(nums):
if not nums: return 0
count = Counter(nums)
max_val = max(nums)
# earn[v] = total points from taking all v's
earn = [v * count[v] for v in range(max_val + 1)]
# Now run house robber on earn
prev2, prev1 = 0, 0
for e in earn:
prev2, prev1 = prev1, max(prev1, e + prev2)
return prev1
print(delete_and_earn([3, 4, 2])) # 6 (take 3+3=no, take 4+2=6)
print(delete_and_earn([2, 2, 3, 3, 3, 4])) # 9 (take all 3s)Ladrão de Casas III: Árvore Binária
Em Ladrão de Casas III, as casas são organizadas como uma árvore binária. Você não pode roubar um nó e seu pai direto simultaneamente. Defina um auxiliar que retorne dois valores: rob(node) → (rob_root, skip_root). Se você roubar a raiz, some os valores de ignorar dos dois filhos. Se ignorar a raiz, some o melhor resultado de cada filho. Essa é uma DFS em pós-ordem com uma decisão de escolher ou ignorar em cada nó.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def rob_tree(root):
def dfs(node):
if not node: return (0, 0) # (rob, skip)
l_rob, l_skip = dfs(node.left)
r_rob, r_skip = dfs(node.right)
rob = node.val + l_skip + r_skip
skip = max(l_rob, l_skip) + max(r_rob, r_skip)
return (rob, skip)
return max(dfs(root))
# Tree: 3 -> 2,3 -> None,3,None,1
root = TreeNode(3, TreeNode(2, None, TreeNode(3)), TreeNode(3, None, TreeNode(1)))
print(rob_tree(root)) # 7Complexidade e Discussão em Entrevistas
O ladrão de casas linear executa-se em tempo O(n) e usa espaço O(1) com a otimização de duas variáveis. A variante circular também executa-se em tempo O(n), pois chama a versão linear duas vezes. A variante em árvore executa-se em tempo O(n) e usa espaço O(h), onde h é a altura da árvore. Em uma entrevista, sempre informe a complexidade depois de programar e mencione a otimização de espaço — isso mostra que você pensa além de uma primeira solução funcional.
# Summary of complexities
# Linear House Robber:
# Time: O(n), Space: O(1) with two-variable trick
# Circular House Robber:
# Time: O(n), Space: O(1) (two passes)
# Tree House Robber:
# Time: O(n), Space: O(h) call stack
# Quick benchmark
import time
import random
nums = [random.randint(0, 100) for _ in range(10**6)]
start = time.time()
prev2 = prev1 = 0
for n in nums:
prev2, prev1 = prev1, max(prev1, n + prev2)
print(f'1M elements in {time.time()-start:.3f}s, result={prev1}')Verificação rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.
Recapitulação da lição
Nesta lição, você aprendeu: a recorrência de escolher ou ignorar dp[i] = max(dp[i-1], nums[i] + dp[i-2]), reduzir o espaço O(n) para O(1) com duas variáveis deslizantes e estender o padrão para vetores circulares e árvores binárias. Em seguida, exploraremos os problemas de Subvetor de Soma Máxima e Subvetor de Produto Máximo usando o algoritmo de Kadane.
Perguntas Frequentes
A aula “House Robber: Recorrência Escolher ou Ignorar” é grátis?
Sim — o texto completo de “House Robber: Recorrência Escolher ou Ignorar” é 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 Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “House Robber: Recorrência Escolher ou Ignorar”?
Modele a decisão de roubar ou ignorar como uma recorrência de DP, reduza o espaço a duas variáveis e estenda a solução para casas dispostas em círculo. Você pratica Coding Interview Prep 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 Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep 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 “House Robber: Recorrência Escolher ou Ignorar”?
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 Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep 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
- House Robber: Recorrência Escolher ou Ignorar
- Subarray Máximo e Subarray de Produto Máximo
- Quebra de Palavras e Segmentação de Strings
- Decodificando Formas e Contando Caminhos