Problem link ও উৎস
- **Original source:** Classic recursion / DP exercise
- **Platform:** LeetCode —
- **Topic:** recursion (decrease-and-conquer → memoization)
- **Difficulty:** Easy
- **Pattern:** decrease-and-conquer, count-the-ways → memoization
- **Basic idea inherited from:** ছদ্মবেশে Fibonacci
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা সিঁড়ির `n`টা ধাপ আছে। তুমি একবারে হয় **1 ধাপ** নয় **2 ধাপ** উঠতে পারো। প্রশ্ন: একদম নিচ থেকে শীর্ষে পৌঁছানোর কতগুলো আলাদা উপায় আছে? তোমার কাজ: সেই উপায়ের সংখ্যা গোনা।
```text
n = 3 হলে উপায়গুলো:
1+1+1
1+2
2+1
মোট = 3 উপায়
```
### Input ও output {#8-example-input-and-output}
```text
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
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি একটা সিঁড়ির গোড়ায় দাঁড়িয়ে, আর প্রতিটা ধাপে একটা নোট আটকানো: "এখান থেকে শীর্ষে যাওয়ার কতগুলো পথ?" তুমি যদি প্রতিবার নতুন করে গোনো, একই ধাপ বহুবার গুনবে। বরং উপরের ধাপ থেকে নিচে নামতে নামতে প্রতিটা ধাপের নোটে উত্তর লিখে রাখো — তাহলে নিচের ধাপের উত্তর শুধু উপরের দুটো নোট যোগ করেই পাওয়া যায়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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 করে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: recurrence-টা সরাসরি code-এ নামাও — শেষ ধাপ 1 বা 2, তাই দুটো branch-এর উপায় যোগ করো।
```text
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/](../../12-dynamic-programming/README.md)-এর bottom-up রূপে গড়ায়।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "সব path গুনব কীভাবে?" ভাবার বদলে জিজ্ঞেস করো "শেষ লাফটা কী ছিল?" শুধু দুটো সম্ভাবনা — 1 বা 2 — আর তখনই problem-টা দুটো ছোট, একই ধরনের problem-এ ভেঙে যায়। এটাই ছদ্মবেশ খুলে Fibonacci বেরিয়ে আসা।
### ছবিতে বোঝা {#7-visual-explanation}
দুটো recursive call, তাই recursion tree। `ways(4)`-এর tree (`ways(1)=1`, `ways(2)=2` base):
```text
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 হয়।
```
### ছোট input-এ ধাপে ধাপে {#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` — উত্তর।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
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)`।
### Output মিলিয়ে দেখা {#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!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
```javascript
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 এড়াতে এটা মনে রেখো।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
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