002 — Climbing Stairs

Source

• Original source: Classic recursion / DP exercise
• Platform: LeetCode — https://leetcode.com/problems/climbing-stairs/
• Topic: recursion (decrease-and-conquer → memoization)
• Difficulty: Easy
• Pattern: decrease-and-conquer, count-the-ways → memoization
• Basic idea inherited from: ছদ্মবেশে Fibonacci

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?

এটা ছদ্মবেশে Fibonacci। শীর্ষে পৌঁছানোর শেষ পদক্ষেপটা হয় 1 ধাপের নয় 2 ধাপের। তাই n-এ পৌঁছানোর উপায় = (n-1 থেকে এক ধাপে) + (n-2 থেকে দুই ধাপে) = ways(n-1) + ways(n-2)। হুবহু Fibonacci recurrence, শুধু base case-গুলো একটু সরানো।

3. What is the hidden math or logic?

লুকানো logic হলো একই recurrence relation: ways(n) = ways(n-1) + ways(n-2)। এর পেছনের যুক্তি — শেষ move-এর উপর ভিত্তি করে সব path-কে দুটো disjoint দলে ভাগ করা: যারা 1 ধাপে শেষ করল, আর যারা 2 ধাপে। দুটো দল overlap করে না, তাই যোগ করা বৈধ (rule of sum)।

4. Which data structure is needed?

Naive recursion-এ শুধু call stack। Optimized version-এ একটা dict (hash map) cache হিসেবে, অথবা মাত্র দুটো variable (prev, curr) — কারণ যেকোনো মুহূর্তে শুধু শেষ দুটো উত্তর দরকার।

5. Why this data structure fits

Cache-টা dict কারণ আমরা n দিয়ে key করে O(1)-তে আগের উত্তর তুলতে চাই — এটাই hash-map lookup। আর যেহেতু ways(n) শুধু ঠিক আগের দুটো value-র উপর নির্ভর করে, পুরো dict-ও লাগে না: দুটো variable rolling করলেই O(1) space-এ চলে। এই O(1) access-ই exponential কাজকে linear করে।

6. Real-life analogy

ভাবো তুমি একটা সিঁড়ির গোড়ায় দাঁড়িয়ে, আর প্রতিটা ধাপে একটা নোট আটকানো: "এখান থেকে শীর্ষে যাওয়ার কতগুলো পথ?" তুমি যদি প্রতিবার নতুন করে গোনো, একই ধাপ বহুবার গুনবে। বরং উপরের ধাপ থেকে নিচে নামতে নামতে প্রতিটা ধাপের নোটে উত্তর লিখে রাখো — তাহলে নিচের ধাপের উত্তর শুধু উপরের দুটো নোট যোগ করেই পাওয়া যায়।

7. Visual explanation

দুটো recursive call, তাই recursion tree। ways(4)-এর tree (ways(1)=1, ways(2)=2 base):

                 ways(4)
                /       \
          ways(3)       ways(2)=2
          /     \
     ways(2)=2  ways(1)=1

ways(3) = 2 + 1 = 3
ways(4) = ways(3) + ways(2) = 3 + 2 = 5

লক্ষ করো: ways(2) এখানেও দুবার লাগছে — repeated subproblem,
তাই cache বসালে প্রতিটা ways(k) একবারই compute হয়।

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 (একটা ধাপ): n = 1 -> Output: 1
Edge case 2 (ছোট base): n = 2 -> Output: 2

9. Brute force thinking

প্রথম সরল চিন্তা: recurrence-টা সরাসরি code-এ নামাও — শেষ ধাপ 1 বা 2, তাই দুটো branch-এর উপায় যোগ করো।

ways(n):
    n <= 2 হলে n ফেরত দাও        (1 ধাপে 1 উপায়, 2 ধাপে 2 উপায়)
    নাহলে ways(n-1) + ways(n-2) ফেরত দাও

10. Why brute force is slow

এই naive recursion O(2^n) — Fibonacci-র মতোই, একই subproblem বারবার নতুন করে compute হয়। ways(40) নিতে হবে কোটি কোটি call, কারণ tree-তে একই node হাজার হাজার বার ফিরে আসে। সেই পুরোনো রোগ: পুনরাবৃত্তি।

11. Key observation

মূল observation: শেষ পদক্ষেপটাই key — শীর্ষে পৌঁছানোর যেকোনো path-এর একদম শেষ লাফ হয় 1 নয় 2। এই দুই দল disjoint আর exhaustive, তাই উত্তর = দুই দলের যোগফল। আর প্রতিটা ways(k) শুধু k-এর উপর নির্ভর করে, তাই cache করা যায়।

12. Optimized intuition

একটা cache (dict) রাখো, অথবা আরও ভালো — শুধু দুটো রোলিং variable। শুরুতে prev = ways(1) = 1, curr = ways(2) = 2; তারপর প্রতিবার prev, curr = curr, prev + curr। n-2 বার ঘোরালে curr-ই উত্তর। এতে time O(n), space O(1)। Cache-ভিত্তিক top-down version-টা সরাসরি ../../12-dynamic-programming/-এর bottom-up রূপে গড়ায়।

13. Thinking tweak

মোচড়: "সব path গুনব কীভাবে?" ভাবার বদলে জিজ্ঞেস করো "শেষ লাফটা কী ছিল?" শুধু দুটো সম্ভাবনা — 1 বা 2 — আর তখনই problem-টা দুটো ছোট, একই ধরনের problem-এ ভেঙে যায়। এটাই ছদ্মবেশ খুলে Fibonacci বেরিয়ে আসা।

14. Step-by-step dry run

Rolling-variable version, n = 5:

1. শুরু: prev = 1 (ways(1)), curr = 2 (ways(2))।
2. step → ways(3): prev, curr = 2, 1+2 = 3। এখন curr = 3।
3. step → ways(4): prev, curr = 3, 2+3 = 5। এখন curr = 5।
4. step → ways(5): prev, curr = 5, 3+5 = 8। এখন curr = 8।
5. তিনবার ঘুরিয়ে (n-2 = 3) curr = 8 — উত্তর।

15. Python solution

from functools import lru_cache

@lru_cache(maxsize=None)
def climb_recursive(n):
    if n <= 2:               # base: 1 ধাপে 1 উপায়, 2 ধাপে 2 উপায়
        return n
    return climb_recursive(n - 1) + climb_recursive(n - 2)

def climb_stairs(n):         # O(1) space, rolling দুটো variable
    if n <= 2:
        return n
    prev, curr = 1, 2        # ways(1), ways(2)
    for _ in range(n - 2):
        prev, curr = curr, prev + curr
    return curr

# ---- tests ----
assert climb_stairs(1) == 1            # একটা ধাপ
assert climb_stairs(2) == 2            # base case
assert climb_stairs(3) == 3
assert climb_stairs(5) == 8
assert climb_recursive(10) == 89       # cached recursion মিলছে
assert climb_stairs(10) == 89
assert climb_recursive(20) == 10946
assert [climb_stairs(i) for i in range(1, 8)] == [1, 2, 3, 5, 8, 13, 21]
print("সব test pass!")

16. Line-by-line code explanation

• if n <= 2: return n — base case দুটো একসাথে: ways(1)=1, ways(2)=2।
• return climb_recursive(n-1) + climb_recursive(n-2) — শেষ লাফ 1 বা 2; দুই branch যোগ।
• @lru_cache — recursive version-এর repeated subproblem cache করে O(n) বানায়।
• prev, curr = 1, 2 — iterative version-এর দুটো রোলিং value।
• prev, curr = curr, prev + curr — এক ধাপ এগোও; শেষ দুটো উত্তর rolling রাখো।
• return curr — n-2 বার ঘোরানোর পর curr-ই ways(n)।

17. Output walkthrough

climb_stairs(5) rolling করে 8 দেয় (dry run-এ দেখানো)। climb_recursive(10) ও climb_stairs(10) দুজনেই 89 — দুই approach মিলছে। climb_recursive(20) cache-এর জোরে দ্রুত 10946 দেয়। শেষ assert প্রথম সাতটা মান (1,2,3,5,8,13,21) মিলিয়ে দেখে, তারপর print: সব test pass!।

18. Time complexity

Naive: O(2^n)। Cached/iterative: O(n) — প্রতিটা ধাপের উত্তর একবার করে বের হয়।

19. Space complexity

Cached recursion: O(n) (stack + cache)। Iterative rolling: O(1) — শুধু দুটো variable।

20. Common mistakes

• base case ভুল বসানো: ways(2) কে 1 ধরা (আসলে 2) — পুরো গোনা বিগড়ে যায়।
• iterative version-এ n-2-এর বদলে n বা n-1 বার ঘোরানো — off-by-one।
• naive recursion দিয়ে বড় n চালিয়ে timeout খাওয়া — cache বা loop ব্যবহার করো।
• n == 0 কে আলাদা না ভাবা (এই problem-এ সাধারণত n >= 1, কিন্তু সীমানা যাচাই করে নাও)।

21. Which basic problem this inherits from

ভিত্তি: Fibonacci Number (এই tracker-এর #1) — হুবহু একই recurrence, শুধু base সরানো। ../patterns.md-এর Pattern 1 (decrease-and-conquer) ও Pattern 7 (memoization) আবার দেখো; আটকে গেলে আগে #1 আবার solve করো।

22. Similar harder problems

• Min Cost Climbing Stairs — https://leetcode.com/problems/min-cost-climbing-stairs/
• House Robber (একই ধরনের "skip বা নাও" recurrence) — https://leetcode.com/problems/house-robber/
• Fibonacci Number (এর parent) — https://leetcode.com/problems/fibonacci-number/ (এই tracker-এর #1)

23. Pattern learned

Count-the-ways via decrease-and-conquer: শেষ পদক্ষেপের উপর ভিত্তি করে path-গুলোকে disjoint দলে ভাগ করো, প্রতিটার count যোগ করো, তারপর repeated subproblem-এ cache বসাও — Fibonacci-আকৃতির counting DP-র মূল রূপ।

24. Final summary

ভবিষ্যতের আমাকে: "Climbing Stairs = ছদ্মবেশে Fibonacci; শেষ লাফ 1 বা 2, তাই ways(n) = ways(n-1) + ways(n-2)।" যখনই কোনো counting problem-এ 'শেষ choice কী ছিল' দিয়ে দুটো (বা কয়েকটা) disjoint দলে ভাগ করা যায় — এই decrease-and-conquer counting pattern মনে করবে।

25. JavaScript solution (with test cases)

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

function climbRecursive(n, cache = new Map()) {   // cached recursion
  if (n <= 2) return n;                 // base: 1 ধাপে 1 উপায়, 2 ধাপে 2 উপায়
  if (cache.has(n)) return cache.get(n);
  const result = climbRecursive(n - 1, cache) + climbRecursive(n - 2, cache);
  cache.set(n, result);
  return result;
}

function climbStairs(n) {               // O(1) space, rolling দুটো variable
  if (n <= 2) return n;
  let prev = 1, curr = 2;               // ways(1), ways(2)
  for (let i = 0; i < n - 2; i++) {
    [prev, curr] = [curr, prev + curr]; // এক ধাপ এগোও
  }
  return curr;
}

// ---- test cases ----
assert(climbStairs(1) === 1, "একটা ধাপ");
assert(climbStairs(2) === 2, "base");
assert(climbStairs(3) === 3, "n=3");
assert(climbStairs(5) === 8, "n=5");
assert(climbRecursive(10) === 89, "cached 10");
assert(climbStairs(10) === 89, "iterative 10");
assert(climbRecursive(20) === 10946, "cached 20");
assert(JSON.stringify([1, 2, 3, 4, 5, 6, 7].map(climbStairs)) === JSON.stringify([1, 2, 3, 5, 8, 13, 21]), "first 7");
console.log("সব JS test pass!");

JS টীকা: [prev, curr] = [curr, prev + curr] হলো destructuring swap — Python-এর prev, curr = curr, prev + curr-এর হুবহু সমতুল্য, ডান পাশ আগে evaluate হয় বলে দুটো value নিরাপদে rolling হয়। এটাই O(1)-space-এ Fibonacci-চাল। iterative version বড় n-এ recursion-এর চেয়ে নিরাপদ (stack overflow নেই)। loop n - 2 বার ঘোরে — off-by-one এড়াতে এটা মনে রেখো।

26. TypeScript solution (with test cases)

function climbStairs(n: number): number {
  if (n <= 2) return n;
  let prev = 1, curr = 2;               // ways(1), ways(2)
  for (let i = 0; i < n - 2; i++) {
    [prev, curr] = [curr, prev + curr];
  }
  return curr;
}

function climbRecursive(n: number, cache: Map<number, number> = new Map()): number {
  if (n <= 2) return n;
  const hit = cache.get(n);
  if (hit !== undefined) return hit;
  const result = climbRecursive(n - 1, cache) + climbRecursive(n - 2, cache);
  cache.set(n, result);
  return result;
}

function expect<T>(a: T, e: T, m = ""): void { if (a !== e) throw new Error(`FAIL ${m}`); }
expect(climbStairs(5), 8, "n5");
expect(climbStairs(10), 89, "n10");
expect(climbRecursive(20), 10946, "rec20");
expect(climbStairs(1), 1, "n1");
expect(climbStairs(2), 2, "n2");
console.log("সব TS test pass!");

TS টীকা: let prev = 1, curr = 2 থেকে TypeScript নিজেই number infer করে, তাই destructuring swap [prev, curr] = [curr, prev + curr]-এ type-mismatch অসম্ভব। climbRecursive-এর cache Map<number, number> এবং hit !== undefined check ways(k) কখনো 0 নয় বলে এখানে কঠোরভাবে দরকার না হলেও — অভ্যাস হিসেবে নিরাপদ idiom। সবকিছু number, তাই counting overflow না হওয়া পর্যন্ত নির্ভুল।

27. কোথায় কাজে লাগে (real-world use)

• Counting paths/ways: "কতভাবে লক্ষ্যে পৌঁছানো যায়" জাতীয় সব counting DP (grid path, decode-ways) এই decrease-and-conquer-এর বংশধর।
• Tiling/combinatorics: 2×n board টাইল করার উপায়, domino-tiling — হুবহু Fibonacci recurrence।
• Step/jump game modeling: game-এ "k ধাপ লাফানোর কত বিন্যাস" হিসাব করতে।
• Financial scenarios: "শেষ সিদ্ধান্ত কী ছিল" দিয়ে disjoint দলে ভাগ করা decision-tree counting।
• Rolling-window optimization: শুধু শেষ দুটো state রাখলেই চলে — এই O(1)-space rolling pattern বহু DP-তে memory বাঁচায়।

এক কথায়, "শেষ choice কী ছিল" দিয়ে path-গুলোকে disjoint দলে ভাগ করে count যোগ করা যায় — দেখলেই এই Fibonacci-আকৃতির counting recurrence (ও তার rolling-variable optimization) মনে করবে।

---

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