Cosecha sin parcelas vecinas
La misión
Problema
Un robot cosechador recorre una sola fila de parcelas, y cada parcela tiene un rendimiento conocido. Su brazo necesita descansar después de cada recolección, así que nunca puede cosechar dos parcelas que estén una al lado de la otra. Devuelve el mayor rendimiento total que el robot puede recoger en una pasada. Los rendimientos son números enteros desde 0 en adelante, y la fila puede estar vacía.
Ejemplos
Input: yields = [2, 7, 9, 3, 1]
Output: 12
Por qué: cosechas las parcelas 0, 2 y 4 para obtener 2 + 9 + 1
Input: yields = [5, 1, 1, 5]
Output: 10
Por qué: las dos parcelas de los extremos no son vecinas, así que se pueden tomar ambas
Input: yields = []
Output: 0
Por qué: caso límite: una fila vacía no rinde nada
Pistas
0 / 3
Tomar primero la parcela más grande puede bloquear dos buenas vecinas. Piensa en la fila parcela por parcela en lugar de toda de golpe.
Cuando llegas a una parcela, enfrentas exactamente una decisión: cosecharla o saltarla. Cada opción solo depende de lo que pasó en la parcela inmediatamente anterior.
Lleva dos totales acumulados: el mejor resultado si la parcela anterior se cosechó y el mejor si se saltó. Cosechar la parcela actual extiende el total de la saltada; saltarla conserva el mejor de los dos.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(1)
Restricciones
- yields are integers ≥ 0
- the row may be empty
Solución
En cada parcela, el mejor total hasta ahora viene de uno de dos estados: la parcela anterior se cosechó o no. Cosechar la parcela actual solo se permite desde el estado en que se saltó la anterior, y saltarla conserva el estado que fuera mejor, así que dos variables reemplazan una tabla completa. La respuesta es el mejor estado después de la última parcela. El tiempo es O(n) con una sola pasada y el espacio es O(1).
def best_harvest(yields):
took, skipped = 0, 0 # best total if the last plot was harvested / left alone
for y in yields:
# harvesting now needs the previous plot skipped; skipping keeps the better state
took, skipped = skipped + y, max(took, skipped)
return max(took, skipped)
print(best_harvest([2, 7, 9, 3, 1])) # -> 12
print(best_harvest([5, 1, 1, 5])) # -> 10
print(best_harvest([])) # -> 0¿Lo que te frena es la idea y no el código? House Robber lo explica.