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 tomar el dinero de las casas que quieras, pero nunca de dos casas que estén una junto a la otra. Devuelve el total más grande que puedas llevarte.
Función
- numsinteger-array
- el dinero de cada casa, en el orden de la calle
- Devuelveinteger
- la cantidad total más grande que puedes tomar sin tomar dinero 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 dan 3 + 3 = 6. La casa del medio por sí sola da 10, y elegirla descarta a sus dos vecinas.
- Entrada
- nums = [2, 9, 3, 1, 8]
- Salida
- 17
- Explicación
- 9 y 8 se encuentran en las casas 1 y 4, que no son vecinas, para sumar 17. Al tomar una casa sí y otra no desde el principio, se obtiene solo 2 + 3 + 8 = 13.
Para ir más allá
Devuelve las casas que hay que llevar y también el total. ¿Qué debes conservar de la tabla para reconstruir esa lista, y pueden hacerlo dos totales acumulados?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Mira la última casa. Un plan la toma o la omite. ¿Qué te queda por resolver con cada opción?
Si omites la casa
k-1, lo mejor es lo mejor de las primerask-1casas. Si la eliges, sumasnums[k-1]a lo mejor de las primerask-2casas. La respuesta parakcasas es la mayor de las dos.Completa esos mejores totales desde el inicio de la calle, empezando con 0 para ninguna casa. Cada uno solo necesita los dos anteriores, así que bastan dos variables.
Solución
Los atajos fallan: saltarse una casa sí y otra no hace que se pierdan 5 y 11 en [5, 3, 4, 11, 2], y elegir primero la casa más rica da un resultado peor con [3, 4, 3]. Decide casa por casa: el mejor total hasta una casa depende únicamente 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
Cualquier plan omite la última casa o la toma. Omitirla deja el mejor plan para las primeras n-1 casas; tomarla suma nums[n-1] al mejor plan para las primeras n-2. Así que most(k) = max(most(k-1), most(k-2) + nums[k-1]), con most(0) = 0 y most(1) = nums[0]. Las dos ramas abarcan todos los planes, así que la respuesta es correcta.
Las ramas se superponen: most(k-1) vuelve a pedir most(k-2), y el número de llamadas crece como los números de Fibonacci, aproximadamente 1.6^n. Cuarenta casas requieren más de 300 millones de llamadas, y n llega a 10^4.
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. - En caso 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 de abajo hacia arriba
Intuición
La recursión solo pregunta por most(0) hasta most(n): n + 1 preguntas. Responde cada una una sola vez en una tabla best, empezando por best[0] = 0 y best[1] = nums[0], y rellenando hacia arriba desde k = 2, para que las dos entradas que lee cada respuesta ya estén allí.
Para [5, 3, 4, 11, 2], la tabla es 0, 5, 5, 9, 16, 16. En k = 4, saltarse la casa 3 mantiene best[3] = 9, mientras que tomar su 11 además de best[2] = 5 da 16, que es mayor. Cada entrada requiere una comparación: tiempo O(n) y espacio O(n).
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 solo lee las dos entradas anteriores, así que conserva dos números en lugar de la tabla: twoBack y oneBack, los mejores totales hasta dos casas atrás y hasta la casa anterior. Para una casa que contiene x, el nuevo mejor total es max(oneBack, twoBack + x); después, desplaza ambos valores. Ambos empiezan en 0, la calle vacía antes de la primera casa, así que una calle con una sola casa no necesita un caso especial. El tiempo sigue siendo O(n), 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 muevecurrentaoneBack. - 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
- Sobrescribir
oneBackantes de copiarlo entwoBack. La siguiente casa lee entonces el total incorrecto. Calcula primero el nuevo máximo y después desplaza los valores, o asigna ambos a la vez. - Leer
nums[1]o establecerbest[1]ybest[2]al principio. Ambas opciones fallan en una calle de una sola casa, como[0]. - En Lua y R, los arreglos empiezan en 1, así que el dinero de la casa
k-1está ennums[k].
Preguntas frecuentes3
¿Cuál es la complejidad temporal y espacial de House Robber?
La programación dinámica examina cada casa una sola 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.
¿Por qué tomar una casa sí y otra no 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 ambas 11, mientras que la primera y la última casa suman 20.
¿Cómo se resuelve House Robber cuando las casas forman un círculo?
En un círculo, la primera y la última casa son vecinas, así que un plan toma 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 sola casa es el 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.
def rob(nums):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumento
nums = [5, 3, 4, 11, 2]
Salida Esperada
16