En ucuz merdiven tırmanışı
Görev tanımı
Problem
Bir merdiven, her basamağa basmak için bir geçiş ücreti alıyor; ücretler i indeksindeki değer i. basamağın ücreti olacak şekilde bir liste olarak veriliyor. Herhangi bir basamaktan bir ya da iki basamak yukarı çıkabilirsin; oraya varmak için ödeme yapmadan 0. ya da 1. basamaktan başlayabilirsin. Son basamağın hemen üstündeki kata ulaşmanın en ucuz toplam ücretini döndür.
Örnekler
Input: cost = [10, 15, 20]
Output: 15
Neden: 1. basamaktan başla, 15 öde, sonra iki basamak atlayıp tepeye çık
Input: cost = [1, 100, 1, 1, 100, 1]
Output: 4
Neden: yalnız ucuz basamaklara basmak toplam dörde mal olur
Input: cost = [5, 3]
Output: 3
Neden: edge case: ucuz basamaktan başlayıp doğrudan dışarı atlamak
İpuçları
0 / 3
Bir yerde durmanın en ucuz yolu yalnız oraya gelebileceğin iki yerde durmanın en ucuz yollarına bağlı.
Tepeden bir rota tahmin etmek yerine aşağıdan yukarı çalış ve iki başlangıç basamağına sıfır maliyet ver.
Sırayla her konum için bir basamak aşağıdan ya da iki basamak aşağıdan gelmenin küçük olanını al ve o basamağın kendi ücretini ekle. Yalnız önceki iki sonuca ihtiyaç duyulduğu için bütün bir tablo yerine onları iki değişkende tut.
- Hedef zaman
- O(n)
- Hedef alan
- O(1)
Çözüm
Herhangi bir konuma yalnız bir ya da iki basamak aşağıdan ulaşılabilir; bu yüzden en ucuz maliyeti, bu iki maliyetin küçüğü artı ayrılan basamağın ücretidir. İki başlangıç basamağında durmak bedavadır, recurrence'ı (yineleme bağıntısı) başlatan da bu. Her adım en fazla iki konum geriye baktığı için iki kayan değişken bütün tablonun yerini alır. Zaman O(n), alan 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])) # -> 3Kodda değil de fikirde mi takıldın? Climbing Stairs bunu anlatıyor.