Merdiven çıkma yolları

Problem

n basamaklı bir merdivenin tepesine çıkacaksın. Her hamlede ya 1 ya da 2 basamak çıkabiliyorsun. Tepeye kaç farklı hamle dizisiyle ulaşabilirsin?

n = 3
1 + 1 + 1
1 + 2
2 + 1
Çıktı: 3

n = 5   -> 8
n = 1   -> 1

Hamlelerin sırası önemlidir: 1 + 2 ile 2 + 1 farklı yollardır.

Netleştirme soruları

• n'nin aralığı ne? (LeetCode'da 1..45. Bu sınır tesadüf değil: n = 45 için cevap int'e sığar, n = 46 taşar.)
• n = 0 tanımlı mı? (Hiç hamle yapmamak tek yol sayılırsa cevap 1.)
• Hamle seti her zaman {1, 2} mi, yoksa genel bir küme mi gelebilir? (Takip sorusu olarak çok sık gelir.)
• Sonuç çok büyükse modulo ile mi döndürülmeli?

İpuçları

Yaklaşım

Anahtar gözlem: n'inci basamağa ulaşan her yolun son hamlesi ya 1'liktir (n - 1'den gelir) ya da 2'liktir (n - 2'den gelir). Bu iki küme ayrıktır ve birlikte tüm yolları kapsar. Dolayısıyla ways(n) = ways(n - 1) + ways(n - 2). Bu Fibonacci dizisidir (bir kaydırmayla).

Naif özyineleme: Formülü doğrudan yazmak O(φⁿ) ≈ O(1,618ⁿ) çağrı yapar; n = 45 için milyarlarca çağrı. Sebep, alt problemlerin üst üste binmesi (overlapping subproblems): ways(n - 2) hem doğrudan hem ways(n - 1) içinden hesaplanır.

Memoization (yukarıdan aşağı): Sonuçları bir dizide sakla; her alt problem bir kez hesaplanır. O(n) zaman, O(n) bellek (dizi + özyineleme stack'i).

Tabulation (aşağıdan yukarı): dp[0..n] dizisini küçükten büyüğe doldur. O(n) zaman, O(n) bellek, özyineleme yok.

Alan optimizasyonu (seçilen çözüm): Sadece son iki değer gerekir; iki değişken yeter. O(n) zaman, O(1) bellek.

Bu soru basit olduğu için asıl öğrettiği şey DP'nin dört adımlık düşünme biçimidir: (1) durumu tanımla, (2) geçişi (rekürans) yaz, (3) temel durumları belirle, (4) hesaplama sırasını ve belleği optimize et. Sonraki tüm DP sorularında aynı adımlar kullanılır.

Java çözümü

public final class ClimbingStairs {

    /** n >= 1; her adımda 1 ya da 2 basamak. */
    public int climbStairs(int n) {
        int twoBelow = 1;                                 // ways(0): hiç basamak yokken 1 yol (hiçbir şey yapma)
        int oneBelow = 1;                                 // ways(1)
        for (int step = 2; step <= n; step++) {
            int current = oneBelow + twoBelow;            // son hamle 1'lik ya da 2'lik
            twoBelow = oneBelow;
            oneBelow = current;
        }
        return oneBelow;
    }
}

ways(0) = 1 ile başlamak hem formülü n = 2 için doğru yapar (1 + 1 = 2) hem de özel durum if (n <= 2) return n gibi dallanmaları ortadan kaldırır.

Karmaşıklık

• Zaman: O(n).
• Bellek: O(1).
• Matris üssü ile O(log n) da mümkündür: [[1,1],[1,0]]^n hızlı üs alma ile hesaplanır. n = 45 için anlamsızdır ama "n = 10^18, sonucu mod 10^9+7 ile ver" takip sorusunda tek doğru cevaptır.

Kenar durumlar ve testler

Testler main içinde çalıştırıldı:

• n = 1: 1; n = 2: 2; n = 3: 3; n = 5: 8.
• n = 1..30 için sonuç, naif özyinelemeli referansla karşılaştırıldı.
• n = 45: 1.836.311.903 (int'e sığıyor; Integer.MAX_VALUE 2.147.483.647).
• n = 46: int taşıyor ve sonuç negatif çıkıyor; test bu taşmayı açıkça doğruluyor. n > 45 gerekiyorsa long (n ≤ 91'e kadar sığar) ya da BigInteger/modulo gerekir.

Mülakatçı için

Bu soru genelde DP'ye ısınma ya da junior/mid seviye bir sorudur; 10 dakikada bitmesi beklenir. Asıl değerlendirme, adayın naif özyinelemenin neden yavaş olduğunu açıklayıp memoization'dan tabulation'a, oradan O(1) belleğe geçiş adımlarını kendisinin atıp atmadığıdır. Taşma sınırını (n = 46) bilen ya da soran aday dikkatli bir mühendis sinyali verir.

İpucu zamanlaması: Aday rekürans ilişkisini 2-3 dakikada kuramazsa ilk ipucunu ver. Naif özyinelemeyi yazıp durursa "n = 45 için kaç çağrı olur?" diye sor. Kalan süreyi takip sorularıyla zorluğu artırmak için kullan; bu soru tek başına seviye ayırt etmez.

Takip sorusu 1: Hamle seti {1, 3, 5} gibi genel bir küme olsun. Beklenen: ways(n) = Σ ways(n - s); O(n · |S|) zaman, O(max(S)) bellek (kayan pencere).

Takip sorusu 2: Her basamağın bir maliyeti var; tepeye en ucuz nasıl çıkılır? Beklenen: toplam yerine minimum: cost(n) = min(cost(n - 1), cost(n - 2)) + c[n] (Min Cost Climbing Stairs, LeetCode 746).

Takip sorusu 3: n = 10^18, cevap mod 10^9+7. Beklenen: 2x2 matris üssü, O(log n); çarpımlarda long ve her adımda mod.

Benzer problemler

• Min Cost Climbing Stairs (LeetCode 746)
• Fibonacci Number (LeetCode 509)
• House Robber (LeetCode 198)
• Decode Ways (LeetCode 91)
• Coin Change II (LeetCode 518)