Subida de escada mais barata
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
O jeito mais barato de estar em algum lugar depende só dos jeitos mais baratos de estar nos dois lugares de onde você poderia ter vindo.
Trabalhe de baixo para cima em vez de adivinhar uma rota a partir do topo, e dê custo zero aos dois degraus iniciais.
Para cada posição, em ordem, pegue o menor valor entre chegar de um degrau abaixo ou de dois degraus abaixo, somando o pedágio daquele degrau. Como só os dois resultados anteriores são necessários, guarde-os em duas variáveis em vez de uma tabela inteira.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(1)
Solução
Só é possível chegar a uma posição a partir de um ou dois degraus abaixo, então o custo mínimo dela é o menor desses dois custos mais o pedágio do degrau de onde se sai. Pisar em qualquer um dos dois degraus iniciais não custa nada, e isso inicializa a recorrência. Como cada passo olha no máximo duas posições para trás, duas variáveis rotativas substituem a tabela inteira. O tempo é O(n) e o espaço é 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])) # -> 3Travou na ideia, e não no código? Climbing Stairs explica isso.