Subida de escalera más barata
La misión
Problema
Una escalera cobra un peaje por pisar cada escalón, dado como una lista donde la posición i guarda el peaje del escalón i. Desde cualquier escalón puedes subir uno o dos escalones, y puedes empezar en el escalón 0 o en el escalón 1 sin pagar por llegar ahí. Devuelve el peaje total más barato para llegar al piso que está justo después del último escalón.
Ejemplos
Input: cost = [10, 15, 20]
Output: 15
Por qué: empiezas en el escalón 1, pagas 15 y saltas dos escalones hasta arriba
Input: cost = [1, 100, 1, 1, 100, 1]
Output: 4
Por qué: pisar solo los escalones baratos cuesta cuatro en total
Input: cost = [5, 3]
Output: 3
Por qué: caso límite: empiezas en el escalón más barato y saltas directo arriba
Pistas
0 / 3
La forma más barata de estar en un lugar depende solo de las formas más baratas de estar en los dos lugares desde los que pudiste venir.
Avanza hacia arriba desde abajo en lugar de adivinar una ruta desde la cima, y dales costo cero a los dos escalones iniciales.
Para cada posición, en orden, toma el menor entre llegar desde un escalón más abajo o desde dos escalones más abajo, sumando el peaje de ese escalón. Como solo se necesitan los dos resultados anteriores, guárdalos en dos variables en lugar de una tabla completa.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(1)
Solución
Solo se puede llegar a una posición desde uno o dos escalones más abajo, así que su costo mínimo es el menor de esos dos costos más el peaje del escalón que se deja atrás. Estar en cualquiera de los dos escalones iniciales no cuesta nada, lo que inicializa la recurrencia. Como cada paso mira como máximo dos posiciones hacia atrás, dos variables que se van actualizando reemplazan la tabla completa. El tiempo es O(n) y el espacio es O(1).
def cheapest_climb(cost):
back2, back1 = 0, 0 # cheapest cost of the two positions behind
for i in range(2, len(cost) + 1):
# arrive from one stair below or two, paying that stair own toll
current = min(back1 + cost[i - 1], back2 + cost[i - 2])
back2, back1 = back1, current
return back1
print(cheapest_climb([10, 15, 20])) # -> 15
print(cheapest_climb([1, 100, 1, 1, 100, 1])) # -> 4
print(cheapest_climb([5, 3])) # -> 3¿Lo que te frena es la idea y no el código? Climbing Stairs lo explica.