002 — Climbing Stairs

Source

• Original source: Classic counting DP exercise
• Platform: LeetCode — https://leetcode.com/problems/climbing-stairs/
• Topic: dynamic programming
• Difficulty: Easy
• Pattern: 1D linear DP (counting)
• Basic idea inherited from: #1 Fibonacci-র recurrence + "count of ways" চিন্তা

1. Problem in simple words

তুমি n-টা সিঁড়ি উঠবে। একবারে হয় 1 ধাপ, নয় 2 ধাপ উঠতে পারো। চূড়ায় পৌঁছানোর কয়টা আলাদা উপায় আছে, সেটা গোনো।

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

2. Which basic idea does this inherit from?

এটা #1 Fibonacci-র উপর দাঁড়ায়। দেখবে recurrence-টা হুবহু Fibonacci — শুধু base case একটু আলাদা। সাথে নতুন একটা চিন্তার ধরন যোগ হয়: count of ways (কতভাবে কাজটা করা যায়), একটা মান বের করা নয়।

3. What is the hidden math or logic?

লুকানো logic: চূড়ায় (step n-এ) ঢোকার শেষ move-টা হয় একটা 1-step (step n-1 থেকে), নয় একটা 2-step (step n-2 থেকে)। এই দুটো দল কখনো overlap করে না (শেষ move আলাদা) আর সব সম্ভাবনা cover করে। তাই step n-এ পৌঁছানোর ways = step n-1-এ পৌঁছানোর ways + step n-2-এ পৌঁছানোর ways।

4. Which data structure is needed?

একটা array (size n+1) tabulation-এর জন্য, যেখানে dp[i] = step i-তে পৌঁছানোর ways। অথবা শুধু দুটো variable — কারণ dp[i] শুধু আগের দুটো cell পড়ে।

5. Why this data structure fits

State এখানে একটামাত্র সংখ্যা: তুমি কোন step-এ আছ। তাই index দিয়ে চলা একটা flat array নিখুঁত — dp[i] step i-এর উত্তর ধরে। আর dependency শুধু পেছনের দুই ঘরে, তাই পুরো array লাগে না; দুটো rolling variable-এ চলে।

6. Real-life analogy

ভাবো সিঁড়ির সামনে দাঁড়িয়ে আছ। যেকোনো ধাপে পৌঁছাতে হলে তোমাকে শেষ লাফটা মারতে হবে — হয় ঠিক নিচের ধাপ থেকে এক লাফ, নয় তার আগের ধাপ থেকে দুই লাফ। তাই কোনো ধাপে পৌঁছানোর মোট পথ = ওই দুই আগের ধাপে পৌঁছানোর পথগুলো একসাথে জোড়া। পথ গুনতে গুনতে উপরে ওঠো।

7. Visual explanation

dp table কীভাবে ভরে — n = 5:

step :  0   1   2   3   4   5
dp   :  1   1   ?   ?   ?   ?      <- base: dp[0]=1, dp[1]=1

dp[2] = dp[1] + dp[0] = 1 + 1 = 2
dp[3] = dp[2] + dp[1] = 2 + 1 = 3
dp[4] = dp[3] + dp[2] = 3 + 2 = 5
dp[5] = dp[4] + dp[3] = 5 + 3 = 8

step :  0   1   2   3   4   5
dp   :  1   1   2   3   5   8     <- answer dp[5] = 8

প্রতিটা ঘর তার পেছনের দুই ঘরের যোগফল (Fibonacci, ছদ্মবেশে)।

8. Example input and output

Input : n = 2  -> Output: 2     (1+1, অথবা 2)
Input : n = 3  -> Output: 3
Input : n = 5  -> Output: 8

Edge case 1: n = 1 -> Output: 1   (একটাই উপায়: এক ধাপ)
Edge case 2: n = 0 -> Output: 1   (কিছু না করেই "চূড়ায়": একটা খালি উপায়)

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা সম্ভাব্য সিদ্ধান্ত recurse করে দেখা — এখান থেকে 1 ধাপ যাই, নাকি 2 ধাপ, আর গোনা।

count(i):
    if i == 0: return 1     # পৌঁছে গেছি, একটা valid উপায়
    if i < 0:  return 0     # লাফ overshoot করল, invalid
    return count(i-1) + count(i-2)

10. Why brute force is slow

এই recursion O(2^n) time নেয় — ঠিক Fibonacci-র মতোই overlapping subproblems। count(5) গুনতে গিয়ে count(3) দুবার, count(2) তিনবার গোনা হয়। n একটু বড় হলেই (যেমন 45) এটা সেকেন্ডের পর সেকেন্ড লাগায়।

11. Key observation

মূল observation: step i-এর উত্তর শুধু i-1 আর i-2-এর উত্তরের উপর নির্ভর করে। তাই প্রতিটা step-এর ways একবার গুনে রেখে দিলে exponential কাজ linear হয়ে যায়।

12. Optimized intuition

State (শব্দে): dp[i] = step i-তে পৌঁছানোর distinct ways-এর সংখ্যা।

Transition:

dp[i] = dp[i-1] + dp[i-2]

কারণ: step i-তে ঢোকার শেষ move হয় i-1 থেকে 1-step, নয় i-2 থেকে 2-step — disjoint আর সম্পূর্ণ।

Base case: dp[0] = 1 (শুরুতে দাঁড়িয়ে থাকার একটাই "উপায়": কিছু না করা), dp[1] = 1।

Answer location: dp[n]।

Memoization (top-down): উপরের recursion-টাই রাখো, একটা dict যোগ করো — solved i reuse করো। Tabulation (bottom-up): ছোট-থেকে-বড় loop দিয়ে array ভরো। যেহেতু শুধু পেছনের দুই cell লাগে, দুটো variable rolling করেও O(1) space-এ করা যায়।

13. Thinking tweak

মোচড়: "কয়টা path আছে গুনব" — এই overwhelming প্রশ্নটাকে বদলে ভাবো "শেষ লাফটা কোথা থেকে এলো?" উত্তর মাত্র দুটো (1-step বা 2-step), তাই বড় count দুটো ছোট count-এর যোগফলে ভেঙে যায়। Counting DP-র এটাই মূল কৌশল: শেষ decision-এর উপর ভাঙো।

14. Step-by-step dry run

n = 4, tabulation দিয়ে:

1. dp = [0,0,0,0,0]; base: dp[0] = 1, dp[1] = 1
2. i = 2: dp[2] = dp[1] + dp[0] = 1 + 1 = 2
3. i = 3: dp[3] = dp[2] + dp[1] = 2 + 1 = 3
4. i = 4: dp[4] = dp[3] + dp[2] = 3 + 2 = 5
5. return dp[4] = 5

হাতে মিলিয়ে দেখো: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 — ঠিক 5 টা। ✔

15. Python solution

# ---- way 1: memoization (top-down) ----
def climb_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:                     # dp[0] = dp[1] = 1
        return 1
    memo[n] = climb_memo(n - 1, memo) + climb_memo(n - 2, memo)
    return memo[n]

# ---- way 2: tabulation (bottom-up) ----
def climb_tab(n):
    if n <= 1:
        return 1
    dp = [0] * (n + 1)
    dp[0], dp[1] = 1, 1            # base cases
    for i in range(2, n + 1):     # small -> large
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

# ---- way 3: O(1) space ----
def climb_fast(n):
    if n <= 1:
        return 1
    a, b = 1, 1                    # ways to reach step 0 and step 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# ---- tests ----
expected = [1, 1, 2, 3, 5, 8, 13, 21]   # n = 0..7
for i, want in enumerate(expected):
    assert climb_memo(i) == want, (i, climb_memo(i))
    assert climb_tab(i) == want, (i, climb_tab(i))
    assert climb_fast(i) == want, (i, climb_fast(i))

assert climb_fast(10) == 89             # বড় n-এ তিনটাই মেলে
assert climb_memo(10) == climb_tab(10) == climb_fast(10)
print("সব test pass!")

16. Line-by-line code explanation

• climb_memo: memo খাতা; n <= 1 দুটো base case একসাথে (দুটোরই উত্তর 1); computed ways memo[n]-এ রাখা হয়।
• climb_tab: dp[0]=dp[1]=1 base; loop ছোট-থেকে-বড়, তাই dp[i-1] ও dp[i-2] আগেই filled; answer dp[n]।
• climb_fast: a = step i-2-এর ways, b = step i-1-এর ways; a, b = b, a + b এক ধাপ এগোয়, পুরো array ছাড়াই।

17. Output walkthrough

expected list-এ n = 0 থেকে 7 পর্যন্ত সঠিক ways (1,1,2,3,5,8,13,21 — Fibonacci-র shifted রূপ)। Loop তিনটা implementation যাচাই করে; তারপর n = 10-এ 89 আর তিন function-এর সমতা check হয়। সব ঠিক থাকলে শেষে print: সব test pass!।

18. Time complexity

তিন version-ই O(n) — প্রতিটা step-এর ways একবার করে গোনা হয়। (Naive recursion ছিল O(2^n)।)

19. Space complexity

• Memoization: O(n) — dict + recursion stack।
• Tabulation: O(n) — dp array।
• Fast version: O(1) — দুটো variable।

20. Common mistakes

• dp[0] = 1 না নিয়ে dp[0] = 0 নেওয়া — তখন সব count শূন্য হয়ে যায়; counting DP-র base সবসময় 1 দিয়ে শুরু (খালি উপায়টা গোনা হয়)।
• "n = 0" আলাদা না ভাবা; এই code-এ n <= 1 সেটা ধরে ফেলে, কিন্তু না ভাবলে array index ভুল হতে পারে।
• 1-step আর 2-step-কে গুলিয়ে শুধু একটা term লেখা (dp[i] = dp[i-1]) — তখন সব উত্তর 1 আসে।

21. Which basic problem this inherits from

ভিত্তি: #1 Fibonacci-র recurrence। ../state-transition-thinking.md-এর "Problem 1 — Climbing Stairs" section-এ ঠিক এই 5-step doctrine হাতে-কলমে দেখানো আছে; recurrence যে Fibonacci তা সেখানেও বলা।

22. Similar harder problems

• Min Cost Climbing Stairs (এখন প্রতিটা ধাপে cost) — https://leetcode.com/problems/min-cost-climbing-stairs/ (এই tracker-এর #3)
• Dice Combinations (1..6 ধাপ, চওড়া look-back) — https://cses.fi/problemset/task/1633 (#4)
• Decode Ways (একই 1/2 ভাঙা, কিন্তু validity শর্তসহ) — https://leetcode.com/problems/decode-ways/

23. Pattern learned

1D counting DP: "কতভাবে?" প্রশ্নকে শেষ decision-এর উপর ভেঙে দাও, আর disjoint case-গুলোর ways যোগ করো। Base case 1 দিয়ে শুরু (খালি উপায়)। Climbing Stairs হলো এই family-র মূল template।

24. Final summary

ভবিষ্যতের আমাকে: "Climbing Stairs = ছদ্মবেশী Fibonacci। State হলো 'step i-তে পৌঁছানোর ways', transition dp[i] = dp[i-1] + dp[i-2], base case 1।" মনে রেখো: counting DP-তে শেষ move-এর উপর ভাঙো আর disjoint case যোগ করো — এই reflex পরের অনেক "count the ways" problem-এ লাগবে।

---

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