Problem link ও উৎস
- **Original source:** Classic counting DP exercise
- **Platform:** LeetCode —
- **Topic:** dynamic programming
- **Difficulty:** Easy
- **Pattern:** 1D linear DP (counting)
- **Basic idea inherited from:** #1 Fibonacci-র recurrence + "count of ways" চিন্তা
## প্রশ্ন ও উদাহরণ {#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
Input : n = 5 -> Output: 8
Edge case 1: n = 1 -> Output: 1 (একটাই উপায়: এক ধাপ)
Edge case 2: n = 0 -> Output: 1 (কিছু না করেই "চূড়ায়": একটা খালি উপায়)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো সিঁড়ির সামনে দাঁড়িয়ে আছ। যেকোনো ধাপে পৌঁছাতে হলে তোমাকে শেষ লাফটা মারতে হবে — হয় ঠিক নিচের ধাপ থেকে এক লাফ, নয় তার আগের ধাপ থেকে দুই লাফ। তাই কোনো ধাপে পৌঁছানোর মোট পথ = ওই দুই আগের ধাপে পৌঁছানোর পথগুলো একসাথে জোড়া। পথ গুনতে গুনতে উপরে ওঠো।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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-এ চলে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা সম্ভাব্য সিদ্ধান্ত recurse করে দেখা — এখান থেকে 1 ধাপ যাই, নাকি 2 ধাপ, আর গোনা।
```text
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:**
```text
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-এর উপর ভাঙো।
### ছবিতে বোঝা {#7-visual-explanation}
`dp` table কীভাবে ভরে — `n = 5`:
```text
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, ছদ্মবেশে)।
```
### ছোট input-এ ধাপে ধাপে {#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 টা। ✔
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
# ---- 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 ছাড়াই।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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 আসে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: #1 Fibonacci-র recurrence। [../state-transition-thinking.md](../state-transition-thinking.md)-এর "Problem 1 — Climbing Stairs" section-এ ঠিক এই 5-step doctrine হাতে-কলমে দেখানো আছে; recurrence যে Fibonacci তা সেখানেও বলা।
### পরের অনুশীলন {#22-similar-harder-problems}
- Min Cost Climbing Stairs (এখন প্রতিটা ধাপে cost) —