Pular para o conteúdo

Subida de escada mais barata

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

A missão

Problema

Uma escada cobra um pedágio para pisar em cada degrau, dado como uma lista em que a posição i guarda o pedágio do degrau i. De qualquer degrau você pode subir um ou dois degraus, e pode começar no degrau 0 ou no degrau 1 sem pagar para chegar lá. Retorne o menor pedágio total para alcançar o andar logo depois do último degrau.

Exemplos

Input:  cost = [10, 15, 20]
Output: 15
Por quê: comece no degrau 1, pague 15 e pule dois degraus até o topo
Input:  cost = [1, 100, 1, 1, 100, 1]
Output: 4
Por quê: pisar só nos degraus baratos custa quatro no total
Input:  cost = [5, 3]
Output: 3
Por quê: edge case: começar no degrau mais barato e pular direto para fora

Dicas

0 / 3

Tempo-alvo
O(n)
Espaço-alvo
O(1)

Travou na ideia, e não no código? Climbing Stairs explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado