LeetCode 70 · Climbing Stairs · Easy
Çözümün her adımını burada izleyebilirsin. Bir n seç, İleri'ye bas ya da Oynat'a tıkla; her basamağın yol sayısının alttaki iki basamaktan nasıl hesaplandığını gör.
Bir basamağa çıkmadan hemen önce ya bir alttaki basamaktaydın ve 1 adım attın, ya da iki alttakindeydin ve 2 adım attın. Başka yolu yok.
Bu yüzden bir basamağa çıkan yol sayısı, bir alttakinin ve iki alttakinin yol sayılarının toplamıdır: 1, 2, 3, 5, 8, 13…
Aşağıdan yukarıya tek bir döngüyle çık. Her turda sadece son iki sonuca ihtiyacın var, o yüzden iki değişken (twoBelow, oneBelow) yeter.
1 ile 12 arasında bir tam sayı yaz. LeetCode 45'e kadar izin veriyor ama merdiven ekrana sığsın diye burada 12 ile sınırlı.
Merdiven (her basamağın üstündeki sayı, oraya kaç farklı yoldan çıkıldığını gösteriyor)
Değişkenler
Kod (Solution.cs içindeki metot)
Her basamağı bir kez hesaplıyoruz: O(n) zaman. Merdiven 5 basamak da olsa 45 basamak da olsa sadece üç sayı tutuyoruz (twoBelow, oneBelow, ways): O(1) bellek.
Aynı formülü kendini çağıran bir metotla (ClimbStairs(n - 1) + ClimbStairs(n - 2)) yazsaydık aynı basamaklar tekrar tekrar hesaplanırdı. n = 5'te bile 3. basamak 2 kez, 2. basamak 3 kez hesaplanır; n = 45'te metot 2 milyardan fazla kez çağrılır ve LeetCode "Time Limit Exceeded" verir.