Problem link ও উৎস
- **Original source:** Classic introductory DP exercise
- **Platform:** LeetCode —
- **Topic:** dynamic programming
- **Difficulty:** Easy
- **Pattern:** 1D linear DP
- **Basic idea inherited from:** plain recursion (folder 06) — `fib(n) = fib(n-1) + fib(n-2)`
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা সংখ্যা `n` দেওয়া হলো। Fibonacci sequence-এর `n`-তম সংখ্যাটা বের করো। Sequence-টা শুরু হয় `0, 1` দিয়ে, তারপর প্রতিটা সংখ্যা তার আগের দুটোর যোগফল।
```text
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) for n >= 2
F(0) থেকে F(8): [0,1,1,2,3,5,8,13,21]
```
এই problem-টা DP শেখার "hello world" — একই জিনিস তিনভাবে লিখবে: memoization, tabulation, তারপর O(1) space।
### Input ও output {#8-example-input-and-output}
```text
Input : n = 2 -> Output: 1 (F(2) = F(1) + F(0) = 1 + 0)
Input : n = 5 -> Output: 5
Input : n = 10 -> Output: 55
Edge case 1: n = 0 -> Output: 0
Edge case 2: n = 1 -> Output: 1
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি সিঁড়ি বেয়ে উঠছ আর প্রতিটা ধাপে আগের দুই ধাপের সংখ্যা যোগ করছ। যদি প্রতিবার নিচ থেকে আবার গুনতে শুরু করো, পাগল হয়ে যাবে। বুদ্ধিমান লোক শুধু **শেষ দুটো ধাপের ফল মনে রাখে**, এক ধাপ এগোয়, পুরোনো সবচেয়ে নিচেরটা ভুলে যায়। সেই "শেষ দুটো মনে রাখা"-ই O(1) DP।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা সরাসরি **recursion** থেকে আসে (folder 06)। `F(n) = F(n-1) + F(n-2)` — এই recurrence-টা চোখে দেখলেই recursive function লেখা যায়। কিন্তু plain recursion এখানে একই sub-প্রশ্ন বারবার করে, তাই আমরা সেই recursion-টাকেই DP দিয়ে smart বানাই — solved উত্তর আর দ্বিতীয়বার compute করি না।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic হলো **overlapping subproblems**। `fib(5)` compute করতে গিয়ে `fib(3)` দুবার, `fib(2)` তিনবার গোনা হয়। মাত্র `n+1`-টা distinct উত্তর (F(0) থেকে F(n)) আছে, কিন্তু naive recursion সেগুলো exponential বার গোনে। প্রতিটা distinct উত্তর একবার গুনে রেখে দিলেই কাজটা O(n) হয়ে যায়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **array** (size `n+1`) tabulation-এর জন্য, বা একটা **dictionary** memoization-এর জন্য। আর O(1) version-এ শুধু **দুটো variable** — কারণ প্রতিটা cell কেবল আগের দুটো cell পড়ে।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
DP-র state এখানে একটা মাত্র সংখ্যা: index `i`। তাই একটা flat array নিখুঁতভাবে state-গুলো ধরে রাখে — `dp[i]` = `F(i)`। যেহেতু `dp[i]` শুধু `dp[i-1]` আর `dp[i-2]` পড়ে, পুরো array লাগেই না; দুটো variable-এ চলে যায়। এটাই standard DP space optimization।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: recurrence-টাকে হুবহু recursion-এ লিখে ফেলা।
```text
fib(n):
if n <= 1: return n
return fib(n-1) + fib(n-2)
```
সঠিক, পড়তে সুন্দর — কিন্তু লুকিয়ে ভয়ংকর।
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এই recursion **O(2^n)** time নেয়, কারণ একই sub-প্রশ্ন বারবার solve করে। `fib(50)` মোটামুটি 2^50-টা call করে মাত্র 51-টা distinct উত্তর বের করতে। Call tree-টা বিশাল কিন্তু তার প্রায় পুরোটাই déjà vu — repeated কাজ। এটাই DP দিয়ে ঠিক করার মূল সমস্যা।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **distinct উত্তর মাত্র `n+1`-টা।** তাহলে প্রতিটা উত্তর একবার গুনে কোথাও লিখে রাখলে, দ্বিতীয়বার আর গোনা লাগে না — exponential কাজ এক ধাক্কায় linear হয়ে যায়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
**State (শব্দে):** `dp[i]` = Fibonacci sequence-এর `i`-তম সংখ্যা, অর্থাৎ `F(i)`।
**Transition:**
```text
dp[i] = dp[i-1] + dp[i-2]
```
**Base case:** `dp[0] = 0`, `dp[1] = 1`।
**Answer location:** `dp[n]`।
এই repo-র doctrine "think top-down, ship bottom-up" মেনে — আগে memoization-এ ভাবো (recursion-এর আয়না), তারপর tabulation-এ ship করো, তারপর space কমাও।
Memoization (top-down): সেই recursion-টাই রাখো, সাথে একটা খাতা (dict)। Solve করার আগে খাতা দেখো, পরে লিখে রাখো।
Tabulation (bottom-up): খাতাটা ছোট-থেকে-বড় order-এ একটা loop দিয়ে ভরো, recursion ছাড়াই।
O(1) space: যেহেতু শুধু আগের দুটো মান লাগে, পুরো array না রেখে দুটো variable `a`, `b` rolling করো।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "সংখ্যাটা recurse করে বের করব" ভাবার বদলে ভাবো "ছোট থেকে শুরু করে একটা একটা করে উপরে উঠব, পথে শুধু শেষ দুটো মান হাতে রাখব।" তাহলে exponential recursion মুহূর্তে একটা simple loop হয়ে যায়।
### ছবিতে বোঝা {#7-visual-explanation}
Tabulation table কীভাবে বাঁ থেকে ডানে ভরে — `n = 8`:
```text
index : 0 1 2 3 4 5 6 7 8
dp : 0 1 ? ? ? ? ? ? ? <- base cases লেখা
ভরা শুরু:
dp[2] = dp[1] + dp[0] = 1 + 0 = 1
dp[3] = dp[2] + dp[1] = 1 + 1 = 2
dp[4] = dp[3] + dp[2] = 2 + 1 = 3
dp[5] = dp[4] + dp[3] = 3 + 2 = 5
dp[6] = dp[5] + dp[4] = 5 + 3 = 8
dp[7] = dp[6] + dp[5] = 8 + 5 = 13
dp[8] = dp[7] + dp[6] = 13 + 8 = 21
index : 0 1 2 3 4 5 6 7 8
dp : 0 1 1 2 3 5 8 13 21 <- answer dp[8] = 21
```
প্রতিটা arrow শুধু বাঁ দিকের দুটো filled cell-এ তাক করে — তাই বাঁ-থেকে-ডান fill order নিরাপদ।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`n = 5`, O(1) version দিয়ে (`a = F(i-1)`, `b = F(i)`):
1. শুরু: `a = 0` (F(0)), `b = 1` (F(1))
2. i = 2: `a, b = b, a + b` → `a = 1, b = 1` (F(2) = 1)
3. i = 3: `a, b = 1, 2` (F(3) = 2)
4. i = 4: `a, b = 2, 3` (F(4) = 3)
5. i = 5: `a, b = 3, 5` (F(5) = 5)
6. loop শেষ। `b = 5` = answer
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
# ---- way 1: memoization (top-down) ----
def fib_memo(n, memo=None):
if memo is None:
memo = {}
if n in memo: # খাতায় আছে? পড়ে নাও
return memo[n]
if n <= 1: # base case
return n
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
return memo[n] # লিখে রাখো, তারপর return
# ---- way 2: tabulation (bottom-up) ----
def fib_tab(n):
if n <= 1:
return n
dp = [0] * (n + 1) # খাতাটা array হিসেবে
dp[0], dp[1] = 0, 1 # base cases আগে লেখা
for i in range(2, n + 1): # fill order: small -> large
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n] # উত্তরের ঠিকানা
# ---- way 3: O(1) space ----
def fib_fast(n):
if n <= 1:
return n
a, b = 0, 1 # a = F(i-1), b = F(i)
for _ in range(2, n + 1):
a, b = b, a + b # এক ধাপ এগোও, পুরোনোটা ভুলে যাও
return b
# ---- tests ----
expected = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
for i, want in enumerate(expected):
assert fib_memo(i) == want, (i, fib_memo(i))
assert fib_tab(i) == want, (i, fib_tab(i))
assert fib_fast(i) == want, (i, fib_fast(i))
assert fib_fast(20) == 6765 # বড় n-এ তিনটাই মেলে
assert fib_memo(20) == fib_tab(20) == fib_fast(20)
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `fib_memo`: `memo` হলো খাতা; `if n in memo` আগের উত্তর reuse করে; base case `n <= 1`; computed মান `memo[n]`-এ লিখে রাখা হয় return-এর আগে।
- `fib_tab`: `dp` array খাতাটা ধরে; `dp[0], dp[1]` base cases; loop ছোট-থেকে-বড় ভরে, তাই `dp[i-1]` ও `dp[i-2]` সবসময় আগেই filled।
- `fib_fast`: `a, b` শুধু শেষ দুটো মান; `a, b = b, a + b` এক assignment-এই দুজনকে এক ধাপ এগিয়ে দেয়, পুরো array লাগে না।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`expected` list-টা F(0) থেকে F(10) পর্যন্ত সঠিক মান। Loop প্রতিটা `i`-তে তিনটা function-ই check করে — সব মিললে assert চুপ থাকে। তারপর `fib_fast(20) == 6765` আর তিন function-এর সমতা যাচাই হয়। সব pass হলে শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
- Memoization: **O(n)** — প্রতিটা distinct `i` একবার করে compute হয়।
- Tabulation: **O(n)** — একবার loop।
- O(1)-space version: **O(n)** — একবার loop।
(Naive recursion ছিল O(2^n) — সেটাই DP fix করল।)
### অতিরিক্ত জায়গা {#19-space-complexity}
- Memoization: **O(n)** — dict + recursion stack।
- Tabulation: **O(n)** — `dp` array।
- Fast version: **O(1)** — শুধু দুটো variable।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- Base case ভুল করা — `F(0)` কে 1 ভাবা; এই সংজ্ঞায় `F(0) = 0`।
- Tabulation-এ `dp = [0]*(n+1)` করার পর `n <= 1` case আলাদা না করা — তখন `n = 0`-এ `dp[1]` index error দেবে।
- O(1) version-এ `a, b = b, a + b`-এর বদলে আলাদা লাইনে `a = b` তারপর `b = a + b` লেখা — দ্বিতীয় লাইনে `a` ততক্ষণে বদলে গেছে, ভুল মান।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: plain recursion (folder 06) — `fib(n) = fib(n-1) + fib(n-2)`। এই folder-এর [../concept.md](../concept.md)-এ ঠিক এই fib দিয়েই memoization আর tabulation introduce করা হয়েছে; [../implementation.py](../implementation.py)-তে runnable version আছে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Climbing Stairs (একই recurrence, ভিন্ন base) —