İçeriğe geç

En ucuz merdiven tırmanışı

Kolay#bottom-up-dp#rolling-variables~20 dk

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

Hedef zaman
O(n)
Hedef alan
O(1)

Kodda değil de fikirde mi takıldın? Climbing Stairs bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case