House Robber: recurrencia de tomar u omitir
Modele la decisión de robar u omitir como una recurrencia de DP, reduzca el espacio a dos variables y amplíe la solución a casas dispuestas en círculo.
House Robber: recurrencia de tomar u omitir es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 1 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
El problema House Robber
El problema House Robber plantea lo siguiente: dado un array de enteros no negativos que representa la cantidad de dinero de cada casa, encuentre la cantidad máxima que puede robar sin robar dos casas adyacentes. Por ejemplo, [2, 7, 9, 3, 1] da como resultado 12 (roba las casas 0, 2 y 4). Este es un problema clásico de DP 1D en el que se toma una decisión binaria en cada paso.
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 12Definición de la recurrencia
Sea dp[i] la cantidad máxima de dinero robada en las primeras i+1 casas. En cada casa i, tiene dos opciones: excluirla (tomar dp[i-1]) o robarla (tomar nums[i] + dp[i-2]). La recurrencia es dp[i] = max(dp[i-1], nums[i] + dp[i-2]). Este es el patrón fundamental de incluir o excluir que aparece en muchos 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])) # 12Recorrido de la tabla de DP
Para [2, 7, 9, 3, 1], recorramos la tabla: 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. La respuesta final es dp[4] = 12. Recorrer manualmente la tabla confirma que la recurrencia gestiona correctamente tanto la inclusión como la exclusión en cada posición.
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])Reducción del espacio a O(1)
La tabla de DP solo consulta las dos posiciones anteriores, así que podemos sustituir el array completo por dos variables: prev2 (dos pasos atrás) y prev1 (un paso atrás). Después de cada iteración, las desplazamos: prev2 = prev1 y prev1 = current. Esto reduce la memoria de O(n) a O(1) y mantiene la complejidad temporal en 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 límite que debe gestionar
Pruebe siempre su solución con casos límite: un array vacío (devuelve 0), un array de un solo elemento (devuelve ese elemento) y un array de dos elementos (devuelve el máximo de los dos). En las entrevistas, mencionar y gestionar estos casos demuestra rigurosidad. La guarda if n == 1 evita el acceso fuera de los límites al consultar 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])) # 10House Robber II: Casas circulares
La variante circular (LeetCode 213) coloca las casas en un círculo, por lo que la primera y la última son adyacentes. No puede aplicar directamente la recurrencia lineal. La idea clave es la siguiente: o bien roba la primera casa y excluye la última, o bien excluye la primera e incluye la última. Ejecute House Robber lineal sobre ambos subarrays y tome el máximo.
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 qué falla greedy aquí
Un enfoque greedy ingenuo podría intentar robar siempre la casa disponible de mayor valor. Sin embargo, falla con entradas como [2, 1, 1, 2]: greedy elige la casa 0 (valor 2) y después la casa 3 (valor 2), con un total de 4, pero robar las casas 0 y 2 también da 3. Espere: en este caso, ¡greedy funciona! Pero pruebe [1, 3, 1, 3, 100]: greedy elige los valores 3 y 3 (índices 1 y 3), con un total de 6, y no alcanza el resultado óptimo de 1+1+100=102. Es necesario usar DP porque las decisiones óptimas a nivel local no garantizan un óptimo 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)) # 102Reconocimiento del patrón de incluir o excluir
El patrón de incluir o excluir se generaliza más allá de House Robber. Cada vez que recorre un array y en cada posición elige entre incluir el elemento actual (y excluir el anterior) o excluirlo (y conservar el resultado anterior), está ante una DP de incluir o excluir. Busque restricciones como no puede haber dos elementos adyacentes o no puede haber intervalos superpuestos como señales para aplicar este patrón.
# 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 Delete and Earn
Delete and Earn (LeetCode 740) plantea lo siguiente: por cada número que elija, obtiene num × count(num), pero debe eliminar todas las apariciones de num-1 y num+1. Esto se reduce directamente a House Robber: construya un array earn[v] = v × count(v) para todos los valores y después ejecute House Robber sobre este array. Reconocer estas reducciones es una habilidad clave en las 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)House Robber III: Árbol binario
En House Robber III, las casas están organizadas como un árbol binario. No puede robar un nodo y su padre directo simultáneamente. Defina una función auxiliar que devuelva dos valores: rob(node) → (rob_root, skip_root). Si roba la raíz, suma los valores de exclusión de ambos hijos. Si excluye la raíz, suma el mejor resultado de cada hijo. Se trata de un DFS en postorden con una decisión de incluir o excluir en cada nodo.
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)) # 7Complejidad y conversación en la entrevista
House Robber lineal se ejecuta en tiempo O(n) y con espacio O(1) gracias a la optimización con dos variables. La variante circular también se ejecuta en tiempo O(n), ya que llama dos veces a la versión lineal. La variante en árbol se ejecuta en tiempo O(n) y con espacio O(h), donde h es la altura del árbol. En una entrevista, indique siempre la complejidad después de programar y mencione la optimización del espacio; demuestra que piensa más allá de una primera solución 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}')Comprobación rápida
Ponga a prueba su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección aprendió: la recurrencia de tomar u omitir dp[i] = max(dp[i-1], nums[i] + dp[i-2]), reducir el espacio de O(n) a O(1) con dos variables rotativas y extender el patrón a arreglos circulares y árboles binarios. A continuación, exploraremos los problemas Maximum Subarray y Maximum Product Subarray mediante el algoritmo de Kadane.
Preguntas frecuentes
¿La lección «House Robber: recurrencia de tomar u omitir» es gratis?
Sí — el texto completo de «House Robber: recurrencia de tomar u omitir» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «House Robber: recurrencia de tomar u omitir»?
Modele la decisión de robar u omitir como una recurrencia de DP, reduzca el espacio a dos variables y amplíe la solución a casas dispuestas en círculo. Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 1 de 4.
¿Cuánto tiempo toma la lección «House Robber: recurrencia de tomar u omitir»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- House Robber: recurrencia de tomar u omitir
- Subarray máximo y subarray de producto máximo
- Word Break y segmentación de strings
- Decode Ways y conteo de rutas