Saltar al contenido

Subida de escalera más barata

Fácil#bottom-up-dp#rolling-variables~20 min

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

Tiempo objetivo
O(n)
Espacio objetivo
O(1)

¿Lo que te frena es la idea y no el código? Climbing Stairs lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio