Problem link ও উৎস
- **Original source:** Classic capstone interview problem (Fibonacci-shaped DP)
- **Platform:** LeetCode —
- **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।
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে `n` ধাপের একটা সিঁড়ি দেওয়া আছে। তুমি একবারে **1 ধাপ বা 2 ধাপ** ওঠো। প্রশ্ন: ঠিক উপরে (ধাপ `n`-এ) পৌঁছানোর কতগুলো আলাদা উপায় আছে? শুধু উপায়ের সংখ্যা return করো।
```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 (একদম ছোট): Input: n = 1 -> Output: 1
Edge case 2 (শূন্য ধাপ): Input: n = 0 -> Output: 1 # একটা খালি পথ
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো প্রতি সকালে একটা ঘরে ঢোকার দুটো দরজা — একটা গতকালের ঘর থেকে, একটা পরশুর ঘর থেকে। আজকের ঘরে পৌঁছানোর মোট পথ = গতকালের পথ + পরশুর পথ। প্রতিদিন শুধু শেষ দু'দিনের হিসাব মনে রাখলেই চলে; তার আগেরটা ভুলে যেতে পারো।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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-এ।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: সরাসরি recursion — শেষ লাফ 1 বা 2 ধরে দুই দিকেই গাছ ছড়াও।
```text
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) লুপে গলে যায়।
### ছবিতে বোঝা {#7-visual-explanation}
`n = 5` পর্যন্ত bottom-up table কীভাবে ভরে:
```text
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)
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `n = 4`:
1. শুরু: `a = 1` (ways(0)), `b = 1` (ways(1))
2. `i = 2`: `c = a + b = 2`; এগোও → `a = 1`, `b = 2`
3. `i = 3`: `c = a + b = 3`; এগোও → `a = 2`, `b = 3`
4. `i = 4`: `c = a + b = 5`; এগোও → `a = 3`, `b = 5`
5. Loop শেষ → return `b = 5`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
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)`।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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` ধরা — তখন পুরো সংখ্যা শিফট হয়ে যায়।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: recursion-এ recurrence লেখা (06 recursion-এর [../../06-recursion-and-backtracking/](../../06-recursion-and-backtracking/README.md)) + overlapping subproblem-কে memo/bottom-up করা (12 DP-র [../../12-dynamic-programming/patterns.md](../../12-dynamic-programming/patterns.md), 1D family)। Fibonacci-র DP রূপ এই দুটোর সরাসরি মিশেল।
### পরের অনুশীলন {#22-similar-harder-problems}
- Min Cost Climbing Stairs (প্রতি ধাপে cost যোগ হয়) —