House Robber
Las casas están en fila a lo largo de una calle, y nums[i] es el dinero que hay en la casa i. Puedes llevarte el dinero de las casas que elijas, pero nunca de dos casas que estén una al lado de la otra. Devuelve la cantidad total máxima que puedes llevarte.
Función
- numsinteger-array
- el dinero de cada casa, en el orden de la calle
- Devuelveinteger
- la suma máxima que puedes llevarte sin tomar nada de dos casas adyacentes
Restricciones
1 ≤ nums.length ≤ 1040 ≤ nums[i] ≤ 1000- La respuesta es como máximo
5 × 106, así que cabe en un entero con signo de 32 bits.
Ejemplos
- Entrada
- nums = [5, 3, 4, 11, 2]
- Salida
- 16
- Explicación
- Toma 5 y 11 de las casas 0 y 3 para obtener 16. Se permite saltarse dos casas seguidas, y en este caso supera a cualquier otro plan: 5 + 4 + 2 = 11 y 3 + 11 = 14.
- Entrada
- nums = [3, 10, 3]
- Salida
- 10
- Explicación
- Las dos casas de los extremos juntas suman 3 + 3 = 6. La casa del medio por sí sola suma 10, y elegirla descarta a sus dos vecinas.
- Entrada
- nums = [2, 9, 3, 1, 8]
- Salida
- 17
- Explicación
- 9 y 8 están en las casas 1 y 4, que no son vecinas, para sumar 17. Tomar una casa sí y otra no desde el principio da solo 2 + 3 + 8 = 13.
+16 pruebas ocultas al enviar
Para ir más allá
Devuelve las casas que se deben llevar, así como el total. ¿Qué tienes que conservar de la tabla para reconstruir esa lista, y los dos totales acumulados aún pueden hacerlo?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Mira la última casa. Un plan o bien la toma o la omite. ¿Qué te deja por resolver cada opción?
Si omites la casa
k-1, el mejor resultado es el mejor de las primerask-1casas. Si la eliges, sumasnums[k-1]al mejor resultado de las primerask-2casas. La respuesta parakcasas es el mayor de los dos.Completa esos mejores totales desde el inicio de la calle, comenzando con 0 para ninguna casa. Cada uno solo necesita los dos anteriores, así que bastan dos variables.
Solución
Los atajos obvios fallan. Elegir una de cada dos casas pasa por alto los planes que se saltan dos casas seguidas, como 5 y 11 en [5, 3, 4, 11, 2], y elegir primero la casa más rica falla con [3, 4, 3], donde 4 bloquea dos casas que juntas valen 6. Lo que funciona es decidir casa por casa: el mejor total hasta una casa depende solo de los mejores totales hasta las dos casas anteriores.
Prueba ambas opciones en cada casa
Correcto, pero no termina con las pruebas más grandes
Intuición
Fíjate en la última casa, la casa n-1. Cualquier plan la omite o la toma. Si la omite, lo mejor que puede hacer es seguir el mejor plan para las primeras n-1 casas. Si la toma, la casa n-2 queda fuera de los límites, así que suma nums[n-1] al mejor plan para las primeras n-2 casas. La respuesta es la mayor de las dos opciones.
Escribe eso como una función most(k), la cantidad máxima que puedes tomar de las primeras k casas: most(k) = max(most(k-1), most(k-2) + nums[k-1]), con most(0) = 0 si no hay casas y most(1) = nums[0] si hay una. Todo plan omite o toma su última casa, así que las dos ramas abarcan todos los planes y el resultado es correcto.
Es lento porque las ramas se solapan. most(k-1) vuelve a llamar a most(k-2), así que la misma pregunta se responde una y otra vez, y la cantidad de llamadas crece como los números de Fibonacci, aproximadamente 1.6^n. Cuarenta casas ya requieren más de 300 millones de llamadas, y las pruebas tienen hasta 10^4 casas. Las llamadas también se anidan hasta una profundidad de n niveles, superando el límite predeterminado de Python de 1000.
Algoritmo
- Escribe una función auxiliar
most(k)que devuelva lo máximo que puedes llevarte de las primeraskcasas. - Devuelve 0 cuando
ksea 0 ynums[0]cuandoksea 1. - De lo contrario, calcula
skip = most(k-1)ytake = most(k-2) + nums[k-1]. - Devuelve el mayor de los dos. La respuesta es
most(n).
def rob(nums):
def most(k):
# The most you can take from the first k houses
if k == 0:
return 0
if k == 1:
return nums[0]
# Skip house k-1, or take it and skip house k-2
return max(most(k - 1), most(k - 2) + nums[k - 1])
return most(len(nums))Tabla ascendente
Intuición
La recursión solo pregunta por most(0) hasta most(n), así que hay n + 1 preguntas diferentes. Responde cada una una sola vez, guárdala en una tabla y rellena la tabla en un orden en el que cada respuesta que leas ya esté ahí. Cuatro decisiones definen la tabla.
Estado: best[k] es lo máximo que puedes llevarte de las primeras k casas. Recurrencia: best[k] = max(best[k-1], best[k-2] + nums[k-1]): saltarse la casa k-1 o llevársela sumándola a lo mejor que termina antes de su vecina. Casos base: best[0] = 0 y best[1] = nums[0]. Orden: k desde 2 hasta n, porque cada entrada lee las dos entradas anteriores.
Para [5, 3, 4, 11, 2], la tabla es 0, 5, 5, 9, 16, 16. En k = 4, comparas saltarte la casa 3, cuyo valor es best[3] = 9, con llevártela, sumando sus 11 a best[2] = 5, y gana 16. La respuesta es la última entrada. Cada entrada requiere una comparación, así que el tiempo es O(n), y la tabla ocupa O(n) de espacio.
Algoritmo
- Crea una tabla
bestcon n + 1 entradas. - Establece
best[0] = 0ybest[1] = nums[0]. - Para
kdesde 2 hasta n, establecebest[k]en el mayor debest[k-1]ybest[k-2] + nums[k-1]. - Devuelve
best[n].
def rob(nums):
n = len(nums)
# best[k] is the most you can take from the first k houses
best = [0] * (n + 1)
best[1] = nums[0]
for k in range(2, n + 1):
# Skip house k-1, or take it on top of the best from the first k-2 houses
best[k] = max(best[k - 1], best[k - 2] + nums[k - 1])
return best[n]Dos totales acumulados
Intuición
Cada entrada de la tabla solo lee las dos entradas que la preceden inmediatamente. Una vez que se conoce best[k], best[k-2] ya no se vuelve a leer. Así que, en lugar de la tabla, guarda dos números: twoBack, el total máximo de las casas hasta dos posiciones atrás, y oneBack, el total máximo hasta la casa anterior.
Para una casa que contiene x, el nuevo máximo es max(oneBack, twoBack + x). Después, desplaza los valores: twoBack toma el valor anterior de oneBack y oneBack toma el nuevo máximo. Ambos empiezan en 0, que representa la calle vacía antes de la primera casa, así que no hace falta tratar la primera casa como un caso especial: su máximo es max(0, 0 + nums[0]).
Con [5, 3, 4, 11, 2], el par pasa por (0, 0), (0, 5), (5, 5), (5, 9), (9, 16), (16, 16), y oneBack termina en 16. El trabajo es el mismo O(n) que con la tabla, y la memoria se reduce a O(1).
Algoritmo
- Establece
twoBackyoneBacken 0. - Para cada cantidad
xennums, calculacurrent = max(oneBack, twoBack + x). - Mueve
oneBackatwoBacky, después,currentaoneBack. - Después de la última casa, devuelve
oneBack.
def rob(nums):
# The best totals from the houses up to two back and up to one back
two_back, one_back = 0, 0
for amount in nums:
# Skip this house, or take it on top of the best from two back
two_back, one_back = one_back, max(one_back, two_back + amount)
return one_back
Errores comunes y casos límite
La mayoría de las respuestas incorrectas se deben a un atajo que funciona con entradas pequeñas o a actualizar los dos totales en el orden equivocado.
- Sumar las casas pares y las casas impares y quedarse con la suma más alta no contempla los planes que se saltan dos casas seguidas. En
[10, 1, 1, 10], ambas sumas son 11, pero las casas 0 y 3 suman 20. - Elegir primero la casa más rica falla con
[3, 4, 3]: eliges 4 y bloqueas ambos 3, que juntos suman 6. - Sobrescribir
oneBackantes de copiarlo entwoBackhace que se pierda el valor que necesita la siguiente casa. Calcula primero el nuevo máximo y después desplaza los valores, o asígnalos ambos a la vez si el lenguaje lo permite. - Leer
nums[1]o establecerbest[1]ybest[2]de antemano falla en una calle con una sola casa. Empezar ambos totales en 0 elimina el caso especial. - En Lua y R, los arreglos empiezan en 1, así que el dinero de la casa
k-1está ennums[k].
Preguntas frecuentes4
¿Cuál es la recurrencia para House Robber?
El mejor total de las primeras k casas es max(best[k-1], best[k-2] + nums[k-1]). O bien omites la casa k-1 y conservas el mejor total de las casas anteriores, o bien tomas la casa k-1 y la sumas al mejor total que termina antes de su vecina. Los casos base son 0 para ninguna casa y nums[0] para una casa.
¿Cuál es la complejidad temporal y espacial de House Robber?
La solución de programación dinámica revisa cada casa una vez, así que tarda O(n). Una tabla completa usa O(n) de espacio, y conservar solo los dos últimos totales lo reduce a O(1). La recursión simple sin respuestas almacenadas realiza alrededor de 1.6^n llamadas, lo que es exponencial.
¿Por qué tomar una de cada dos casas no resuelve el problema del ladrón de casas?
El mejor plan a veces se salta dos casas seguidas. En [10, 1, 1, 10], las casas pares y las casas impares suman 11, mientras que llevarse la primera y la última casa da 20. La programación dinámica compara las opciones de saltarse y llevarse cada casa, así que encuentra esos planes.
¿Cómo resuelves el problema del ladrón de casas cuando las casas forman un círculo?
En un círculo, la primera y la última casa son vecinas, así que un plan puede incluir como máximo una de ellas. Ejecuta dos veces la solución para una calle recta: una vez sin la última casa y otra sin la primera, y devuelve el resultado mayor. Una calle con una sola casa es el único caso especial: la respuesta es esa casa.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def rob(nums):
# Escribe el código aquíCaso 1
Caso 2
Caso 3
Entrada
nums = [5, 3, 4, 11, 2]
Esperado
16