002 — Climbing Stairs¶

Source¶

Original source: Classic capstone interview problem (Fibonacci-shaped DP)
Platform: LeetCode — https://leetcode.com/problems/climbing-stairs/
Topic: recursion + dynamic programming
Difficulty: Easy
Pattern: 1D DP (bottom-up Fibonacci recurrence)
Basic idea inherited from: এটা একটা cross-topic capstone — এখানে মেশে 06 recursion (সমস্যাকে ছোট সমস্যায় ভাঙা: শেষ ধাপটা 1 না 2) আর 12 dynamic programming (একই sub-answer বারবার না করে cache/roll করা)। কাঁচা recursion → memo → bottom-up — এই তিন রূপের প্রতিটাই এই combo।

1. Problem in simple words¶

তোমাকে n ধাপের একটা সিঁড়ি দেওয়া আছে। তুমি একবারে 1 ধাপ বা 2 ধাপ ওঠো। প্রশ্ন: ঠিক উপরে (ধাপ n-এ) পৌঁছানোর কতগুলো আলাদা উপায় আছে? শুধু উপায়ের সংখ্যা return করো।

n = 3 হলে উপায়গুলো:
  1 + 1 + 1
  1 + 2
  2 + 1
মোট = 3 উপায়

2. Which basic idea does this inherit from?¶

এই problem দুটো আগের chapter-এর tool জোড়া দেয়:

06 recursion থেকে: "ধাপ n-এ পৌঁছানোর শেষ লাফটা হয় 1, নয় 2" — তাই ways(n) = ways(n-1) + ways(n-2)। বড় সমস্যা দুটো ছোট সমস্যায় ভেঙে যায়।
12 dynamic programming থেকে: কাঁচা recursion একই ways(k) বহুবার গোনে (overlapping subproblems), তাই উত্তর cache বা roll করতে হয়।

একা recursion দেয় recurrence; একা DP দেয় repeat কাজ মুছে ফেলা। দুটো মিললে O(n)।

3. What is the hidden math or logic?¶

লুকানো logic একটা Fibonacci recurrence: ধাপ n-এ আসতে হলে তোমার ঠিক আগের অবস্থা ছিল হয় ধাপ n-1 (তারপর 1 লাফ), নয় ধাপ n-2 (তারপর 2 লাফ) — আর কোনো পথ নেই। তাই ways(n) = ways(n-1) + ways(n-2), base: ways(0)=1, ways(1)=1। সংখ্যাগুলো ঠিক Fibonacci sequence।

4. Which data structure is needed?¶

কোনো বড় data structure লাগে না — bottom-up করলে শুধু দুটো integer variable (a, b) যথেষ্ট। (memo রূপে একটা array/dict-ও চলে, কিন্তু rolling দুই variable সবচেয়ে পরিষ্কার — এটাই 12 DP-র space trick।)

5. Why this data structure fits¶

প্রতিটা ways(n) শুধু আগের ঠিক দুটো মান-এর উপর নির্ভর করে — তার আগের সব মান লাগে না। তাই পুরো DP table না রেখে শুধু শেষ দুটো সংখ্যা গড়িয়ে নিয়ে গেলেই হয় (06 recursion-এর recurrence + 12 DP-র rolling-state)। এজন্যই দুটো variable পুরো কাজটা করে দেয়, O(1) space-এ।

6. Real-life analogy¶

ভাবো প্রতি সকালে একটা ঘরে ঢোকার দুটো দরজা — একটা গতকালের ঘর থেকে, একটা পরশুর ঘর থেকে। আজকের ঘরে পৌঁছানোর মোট পথ = গতকালের পথ + পরশুর পথ। প্রতিদিন শুধু শেষ দু'দিনের হিসাব মনে রাখলেই চলে; তার আগেরটা ভুলে যেতে পারো।

7. Visual explanation¶

n = 5 পর্যন্ত bottom-up table কীভাবে ভরে:

ways(0) = 1            (কিছু না উঠেই "পৌঁছে গেছি", একটা খালি পথ)
ways(1) = 1            (শুধু 1)
ways(2) = ways(1)+ways(0) = 1+1 = 2
ways(3) = ways(2)+ways(1) = 2+1 = 3
ways(4) = ways(3)+ways(2) = 3+2 = 5
ways(5) = ways(4)+ways(3) = 5+3 = 8

rolling দুই variable: (a,b) = (1,1) -> (1,2) -> (2,3) -> (3,5) -> (5,8)

8. Example input and output¶

Input : n = 2   -> Output: 2      # (1+1), (2)
Input : n = 3   -> Output: 3      # (1+1+1), (1+2), (2+1)
Input : n = 5   -> Output: 8

Edge case 1 (একদম ছোট): Input: n = 1  -> Output: 1
Edge case 2 (শূন্য ধাপ): Input: n = 0  -> Output: 1   # একটা খালি পথ

9. Brute force thinking¶

প্রথম সরল চিন্তা: সরাসরি recursion — শেষ লাফ 1 বা 2 ধরে দুই দিকেই গাছ ছড়াও।

def ways(n):
    if n <= 1: return 1
    return ways(n-1) + ways(n-2)

10. Why brute force is slow¶

এই recursion একই ways(k) বারবার গোনে — ways(5) ডাকে ways(4) আর ways(3), ways(4) আবার ডাকে ways(3)... call tree-টা O(2^n)-এ ফুলে ওঠে। ঠিক এই repeated subproblem-ই 12 dynamic programming মুছতে আসে (memo বা bottom-up দিয়ে)।

11. Key observation¶

মূল observation: ways(n) শুধু আগের দুটো মান ways(n-1) আর ways(n-2)-এর উপর নির্ভরশীল — পুরো call tree ফের গোনার দরকার নেই, শুধু শেষ দুটো সংখ্যা মনে রাখলেই হয়। এই এক চিন্তাই O(2^n) → O(n) করে দেয়।

12. Optimized intuition¶

ছোট থেকে বড় দিকে যাও (bottom-up)। দুটো variable a = ways(i-2), b = ways(i-1) রাখো; প্রতি step-এ নতুন ways(i) = a + b বের করে দুজনকে এক ঘর এগিয়ে দাও। n step পরে b-ই উত্তর। recursion-এর কোনো stack নেই, repeat কাজ নেই।

13. Thinking tweak¶

মোচড়: "উপর থেকে নিচে সব পথ গুনব" ভাবার বদলে ভাবো "নিচ থেকে উপরে উঠি, শুধু শেষ দুটো সংখ্যা গড়িয়ে নিয়ে।" exponential গাছ একটা O(n) লুপে গলে যায়।

14. Step-by-step dry run¶

Input n = 4:

শুরু: a = 1 (ways(0)), b = 1 (ways(1))
i = 2: c = a + b = 2; এগোও → a = 1, b = 2
i = 3: c = a + b = 3; এগোও → a = 2, b = 3
i = 4: c = a + b = 5; এগোও → a = 3, b = 5
Loop শেষ → return b = 5

15. Python solution¶

def climb_stairs(n):
    a, b = 1, 1            # a = ways(i-2), b = ways(i-1); ways(0)=ways(1)=1
    for _ in range(n - 1): # n-1 বার গড়ালে b = ways(n)
        a, b = b, a + b    # এক ঘর সামনে: নতুন b = আগের দুটোর যোগ
    return b

# ---- tests ----
assert climb_stairs(1) == 1
assert climb_stairs(2) == 2
assert climb_stairs(3) == 3
assert climb_stairs(5) == 8
assert climb_stairs(10) == 89     # Fibonacci: 1,1,2,3,5,8,13,21,34,55,89
print("সব test pass!")

16. Line-by-line code explanation¶

a, b = 1, 1 — base case: ধাপ 0-এ পৌঁছানোর 1 উপায় (খালি পথ), ধাপ 1-এ 1 উপায়।
for _ in range(n - 1) — b-কে ways(1) থেকে ways(n) পর্যন্ত আনতে ঠিক n-1 বার গড়াতে হয়।
a, b = b, a + b — recurrence-টা rolling রূপে: নতুন b = আগের দুটোর যোগ, আর a এক ঘর এগোয় (06 recurrence + 12 rolling DP)।
return b — লুপ শেষে b ধরে রাখে ways(n)।

17. Output walkthrough¶

n = 5-এ (a,b) চলে (1,1) -> (1,2) -> (2,3) -> (3,5) -> (5,8), return b = 8 — assert pass। n = 1-এ লুপ একবারও চলে না, return শুরুর b = 1। n = 10-এ Fibonacci গড়িয়ে 89 দেয়। শেষে print: সব test pass!।

18. Time complexity¶

O(n) — একটা লুপ n-1 বার, প্রতিবার O(1) কাজ।

19. Space complexity¶

O(1) — শুধু দুটো integer (a, b); recursion stack নেই, table নেই (12 DP-র rolling-state)।

20. Common mistakes¶

লুপ n বার চালানো (n-1-এর বদলে) — তখন এক ঘর বেশি গড়িয়ে ভুল উত্তর।
কাঁচা recursion ছেড়ে না দেওয়া — বড় n-এ O(2^n) timeout করে; memo বা bottom-up লাগবেই।
ways(0) = 1 ভুলে 0 ধরা — তখন পুরো সংখ্যা শিফট হয়ে যায়।

21. Which basic problem this inherits from¶

ভিত্তি: recursion-এ recurrence লেখা (06 recursion-এর ../../06-recursion-and-backtracking/) + overlapping subproblem-কে memo/bottom-up করা (12 DP-র ../../12-dynamic-programming/patterns.md, 1D family)। Fibonacci-র DP রূপ এই দুটোর সরাসরি মিশেল।

22. Similar harder problems¶

Min Cost Climbing Stairs (প্রতি ধাপে cost যোগ হয়) — https://leetcode.com/problems/min-cost-climbing-stairs/
House Robber (পরপর দুটো নেওয়া যায় না, একই রকম recurrence) — https://leetcode.com/problems/house-robber/
Fibonacci Number — https://leetcode.com/problems/fibonacci-number/
Decode Ways (1/2-অঙ্ক "লাফ"-এর string সংস্করণ) — https://leetcode.com/problems/decode-ways/

23. Pattern learned¶

1D bottom-up DP (Fibonacci recurrence): "শেষ ধাপটা 1 না 2" ভেঙে f(n)=f(n-1)+f(n-2) পেয়ে, শুধু শেষ দুটো মান গড়িয়ে O(n)/O(1)-এ পৌঁছানো — recursion + DP combo-র সবচেয়ে মৌলিক রূপ।

24. Final summary¶

ভবিষ্যতের আমাকে: "ছোট ছোট লাফে শেষ পর্যন্ত পৌঁছানোর উপায় গোনা" দেখলেই Fibonacci-DP মনে করবে। আগে recurrence লেখো (শেষ লাফটা কী কী হতে পারে), তারপর সেটাকে দুই-variable rolling-এ নামাও। mock-এ এটা warm-up — দ্রুত, পরিষ্কার, off-by-one ছাড়া লিখতে পারা চাই।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।