Climbing Stairs
n basamaklı bir merdivenin en altındasın. Her hamlede 1 veya 2 basamak çıkarsın. Hamle dizileri farklı olduğunda çıkış biçimleri de farklı sayılır; dolayısıyla 1, 2 ve 2, 1 iki ayrı yoldur. Fonksiyonun n değerini alır ve tepeye ulaşmanın farklı yollarının sayısını döndürür.
Fonksiyon
- ninteger
- merdivendeki basamak sayısı
- Döndürürinteger
- n. adıma ulaşan 1 adımlı ve 2 adımlı farklı dizilerin sayısı
Kısıtlar
1 ≤ n ≤ 45- The answer fits in a signed 32-bit integer:
n = 451836311903değerini verir.
Örnekler
- Girdi
- n = 3
- Çıktı
- 3
- Açıklama
- Üç basamak
1, 1, 1,1, 2veya2, 1şeklinde çıkılabilir; yani 3 yol vardır.
- Girdi
- n = 5
- Çıktı
- 8
- Açıklama
- 5. adıma yapılan her tırmanış, 4. adımdan 1 adımlık (oraya ulaşmanın 5 yolu vardır) ya da 3. adımdan 2 adımlık (3 yolu vardır) bir tırmanışla sona erer; bu yüzden cevap
5 + 3 = 8olur.
Gönderirken +13 gizli test
Ek soru
Ya bazı basamaklar bozuksa ve üzerlerine asla çıkamıyorsan ne olur? Özyineleme nasıl değişir ve bozuk bir basamak için sayı kaçtır?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
nadımına yapılan herhangi bir tırmanışın son hareketine bak. Bu hareketten hemen önce nerede durmuş olabilirdin?nbasamağına yapılan her tırmanış, yan-1basamağından 1 adımla ya dan-2basamağından 2 adımla sona erer; ikisi birden asla olmaz. Bu nedenleniçin sayı,n-1için sayı ilen-2için sayının toplamıdır.1 adım (1 yol) ve 2 adım (2 yol) için sayılardan başlayıp ilerleyin. Yalnızca son iki sayıya ihtiyacınız vardır ve her yeni sayı bunların toplamıdır.
Çözüm
Her tırmanışı listelemek işe yaramaz: 45 basamaklı bir merdivende 1836311903 farklı tırmanış vardır. Çözüm, son harekettir. n. basamağa ulaşan her tırmanış, bitişten hemen önce n-1. veya n-2. basamaktan geçer; bu da Fibonacci bağıntısı olan ways(n) = ways(n-1) + ways(n-2) ifadesini verir. Bunu alttan üste doğru hesaplayın; ihtiyacınız olan tek şey iki değişkendir.
Son hamle üzerinde düz özyineleme
Doğru, ama en büyük testlerde bitmiyor
Sezgi
n basamağına çıkan yolları son adımlarına göre ayırın. 1 adımla biten bir çıkışta, bu adımdan önce n-1 basamağında durulmuştur ve bu türden ways(n-1) çıkış vardır. 2 adımla biten bir çıkışta ise n-2 basamağında durulmuştur ve bu türden ways(n-2) çıkış vardır. Her çıkış bu iki yoldan biriyle biter ve hiçbiri her iki yoldan birden bitmez; dolayısıyla ways(n) = ways(n-1) + ways(n-2).
Özyinelemenin iki temel duruma ihtiyacı vardır. Bir basamağın bir çıkışı, iki basamağın ise iki çıkışı vardır (1, 1 ve 2). Her iki durumda da yanıt n'e eşittir; bu nedenle fonksiyon, n ≤ 2 olduğunda n'i, aksi hâlde toplamı döndürür.
Yanıt doğru, ancak işlem miktarı katlanarak artar. climbStairs(5), 3. basamağı iki kez ve 2. basamağı üç kez hesaplar; toplamda 9 çağrı yapar ve çağrı sayısı yanıtların kendisi gibi büyür. n = 45 için fonksiyon 2269806339 çağrı yapar; bu yaklaşık 2.3 × 10^9 çağrıdır ve zaman sınırı için çok fazladır. Özyineleme yalnızca n düzey derinliğindedir; dolayısıyla yığın O(n) alan kullanır.
Algoritma
- Eğer
n ≤ 2isendeğerini döndür. - Özyinelemeli bir çağrıyla
n-1basamağına ulaşan tırmanışları say. - İkinci bir özyinelemeli çağrıyla
n-2basamağına ulaşan tırmanışları say. - İki sayının toplamını döndür.
def climbStairs(n):
if n <= 2:
return n # 1 step: one way, 2 steps: two ways
return climbStairs(n - 1) + climbStairs(n - 2)Önbellek kullanarak özyineleme
Sezgi
Özyineleme yalnızca unuttuğu için yavaştır. Her sayı yalnızca k değerine bağlıdır; bu nedenle k adımının sayısını bir kez öğrendiğinde bu sayı artık değişmez. Bir bellek tablosu, her adım için bir yuvası olan bir dizi tut ve her sayıyı ilk hesapladığında oraya yaz. Aynı adım için sonraki her istekte yeniden özyinelemeye başvurmak yerine yuvadaki değeri oku.
Artık 3. adımdan n. adıma kadar olan sayıların her biri bir kez ve tek bir toplamayla hesaplanır. n = 5 için çağrılar bir kez 2. adıma kadar iner, ardından yanıtlar 3, 5 ve 8 olarak yukarı çıkar ve 3. adım için ikinci istek belleğe bakılarak karşılanır. Bu, milyarlarca çağrı yerine O(n) zaman demektir.
Bellek tablosu n + 1 sayı tutar ve özyineleme hâlâ n düzey derinliğindedir; dolayısıyla alan karmaşıklığı O(n) olur. Bir yuvadaki 0, değerin henüz bilinmediği anlamına gelir; bu güvenlidir, çünkü gerçek her sayı en az 1'dir.
Algoritma
- Hepsi 0 olan
n + 1yuvalı bir önbellek oluştur. - Özyinelemeli yardımcı işlevde,
k ≤ 2olduğundakdeğerini döndür. kiçin önbellek yuvası 0 ise, bu yuvayı yardımcı işlevink-1vek-2için döndürdüğü sonuçların toplamıyla doldur.- Önbellek yuvasını döndür.
- Yardımcı işlevi
nüzerinde çağır.
def climbStairs(n):
memo = [0] * (n + 1) # memo[k] = ways to reach step k, 0 = not known yet
def ways(k):
if k <= 2:
return k
if memo[k] == 0:
memo[k] = ways(k - 1) + ways(k - 2)
return memo[k]
return ways(n)İki değişkenle alttan yukarıya
Sezgi
Özyinelemeyi tersine çevirin. En üstten başlayıp aşağıya doğru sormak yerine, en alttan başlayıp yukarı doğru ilerleyin. k adımı için sayıyı hesapladığınızda, k-1 ve k-2 adımlarının sayıları zaten bilinir ve daha eski hiçbir değer tekrar okunmaz. Böylece tüm önbelleğin yerini iki değişken alır.
prev, k-2 adımının sayısını; curr ise k-1 adımının sayısını tutsun. 1. ve 2. adımların sayıları olan prev = 1 ve curr = 2 ile başlayın. Her adımda bunları toplayıp next değişkenine atayın, ardından ikiliyi bir adım ileri kaydırın. n = 5 için ikili (1, 2) değerinden (2, 3), (3, 5) ve (5, 8) değerlerine ilerler ve yanıt curr = 8 olur.
Döngü, her seferinde bir toplama işlemi yaparak n-2 kez çalışır; zaman karmaşıklığı O(n)'dir ve üç tam sayı saklar; alan karmaşıklığı O(1)'dir. prev değerinin üzerine yazmadan önce next değerini hesaplayın; yoksa toplamda yanlış değer kullanılır.
Algoritma
- Eğer
n ≤ 2isendeğerini döndür. prev = 1vecurr = 2olarak ayarla.- 3'ten
n'ye kadarkiçinnext = prev + currdeğerini hesapla, ardındanprev = currvecurr = nextolarak ayarla. currdeğerini döndür.
def climbStairs(n):
if n <= 2:
return n
prev, curr = 1, 2 # ways to reach steps 1 and 2
for _ in range(n - 2):
prev, curr = curr, prev + curr
return curr
Tuzaklar ve uç durumlar
Yineleme kısa olduğundan hataların çoğu temel durumlarda, çalışma süresinde ve 32 bit sınırında ortaya çıkar.
- Basit özyinelemeli çözümü teslim etmek. Küçük testleri geçer, ancak
n = 45için yaklaşık2.3 × 10^9çağrı gerekir. Her sayıyı yalnızca bir kez hesaplayıp saklayın. - Yanlış temel durumlar. İki basamak için iki çıkış yolu vardır:
1, 1ve2.n = 2için 1 döndürmek sonraki tüm yanıtları kaydırır:n = 3için 3 yerine 2 elde edersiniz. - Diziler yerine seçimleri saymak.
1, 2ve2, 1iki ayrı çıkış yoludur. Yalnızca kaç tane 2 basamak çıktığınızı saymakn/2 + 1verir; bu dan = 5için 8 yerine 3'tür. - Kontrol eklemeden tablo doldurmak.
n = 1olduğundan + 1 = 2yuvalı bir tabloda 2. basamağın sayısı için yer yoktur.n ≤ 2olduğunda hemenndöndürün. - Bir adım fazla ilerlemek. 45 basamağın sayısı olan 1836311903, 32 bite sığar; ancak 46 basamağın sayısı olan 2971215073 sığmaz. Fazladan bir değer hesaplayan döngü, Java, C veya C# dilinde taşma nedeniyle negatif bir sayıya dönüşür.
Sıkça sorulan sorular4
Merdivenleri Tırmanma problemi neden bir Fibonacci problemidir?
n basamağına yapılan her tırmanış, n-1 basamağından 1 basamaklık veya n-2 basamağından 2 basamaklık bir adımla sona erer; dolayısıyla ways(n) = ways(n-1) + ways(n-2). Bu, Fibonacci kuralıdır. ways(1) = 1 ve ways(2) = 2 olduğunda sayılar 1, 2, 3, 5, 8, 13 şeklinde ilerler; bu da bir basamak kaydırılmış Fibonacci dizisidir: ways(n) = F(n+1).
Climbing Stairs algoritmasının zaman karmaşıklığı nedir?
Alttan üste döngüsü n-2 toplama yapar; bu nedenle O(n) zamanda ve O(1) ek alanla çalışır. Düz özyineleme üstel karmaşıklıktadır: çağrı sayısı her adımda yaklaşık 1.618 katına çıkar ve n = 45 için 2269806339'a, yani yaklaşık 2.3 × 10^9'a ulaşır. Önbellekleme, özyinelemeyi O(n) zamana ve O(n) alana indirir.
Önbelleğe alma ile aşağıdan yukarıya çözüm arasındaki fark nedir?
Memoizasyon özyinelemeli işlevi korur ve her sonucu ilk hesaplandığında önbelleğe alır; bu nedenle yukarıdan aşağıya çalışır ve çağrı yığınına ve bir tabloya ihtiyaç duyar. Aşağıdan yukarıya döngüsü sayımları artan sırayla hesaplar; böylece ihtiyaç duyduğu her değer zaten bilinir ve özyineleme kullanılmaz. Her ikisi de O(n) işlem yapar. Döngü ayrıca tabloyu bırakıp iki sayıyı tutmanıza olanak tanır.
1, 2 veya 3 adımlık hamlelerle Merdiven Çıkma problemini nasıl çözersiniz?
Tırmanışları son hamlelerine göre tekrar ayır: ways(n) = ways(n-1) + ways(n-2) + ways(n-3). ways(0) = 1 (boş tırmanış), ways(1) = 1 ve ways(2) = 2 değerlerinden başla ve iki yerine son üç sayıyı sakla. Zaman karmaşıklığı O(n), alan karmaşıklığı ise O(1) olarak kalır.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def climbStairs(n):
# Kodu buraya yazınDurum 1
Durum 2
Girdi
n = 3
Beklenen
3