# Dynamic programming — টেবিল কীভাবে উত্তর তৈরি করে

[অধ্যায়ের সূচি](README.md) · [সহজ ব্যাখ্যা ও বাস্তব ব্যবহার](learning-guide.md) · [অনুশীলন ও সমাধান](problems/README.md)

DP-তে প্রতিটি cell একটি ছোট প্রশ্নের উত্তর রাখে। নতুন cell হিসাব করতে আগেই জানা cell ব্যবহার করি। আগে প্রশ্নটি কী, তারপর **কোন cell থেকে কোন cell-এর মান আসছে**, তা দেখো।

## Grid paths — ওপরের ও বাঁয়ের উত্তর যোগ

একটি 3×3 grid-এ ওপরের বাঁ কোণ থেকে নিচের ডান কোণে যেতে হবে। শুধু right ও down চলা যায়। `dp[r][c]` মানে ওই ঘরে পৌঁছানোর পথসংখ্যা; তাই `dp[r][c] = ওপরের মান + বাঁয়ের মান`।

```dsa
kind: grid
title: চার ধাপে পুরো path table
steps:
  - label: ১. শুরুতে দাঁড়ানোর একটি উপায়
    rows: [[1, '·', '·'], ['·', '·', '·'], ['·', '·', '·']]
    active: [[0, 0]]
    note: Base case dp[0][0] = 1। বিন্দু মানে এখনো হিসাব হয়নি।
  - label: ২. প্রথম সারি
    rows: [[1, 1, 1], ['·', '·', '·'], ['·', '·', '·']]
    active: [[0, 1], [0, 2]]
    note: ওপরের ঘর নেই; শুধু বাঁ দিক থেকে আসা যায়। তাই দুটো মানই 1।
  - label: ৩. দ্বিতীয় সারি
    rows: [[1, 1, 1], [1, 2, 3], ['·', '·', '·']]
    active: [[1, 0], [1, 1], [1, 2]]
    note: বাঁ থেকে ডানে 1, তারপর 1+1 = 2, তারপর 1+2 = 3।
  - label: ৪. শেষ সারি
    rows: [[1, 1, 1], [1, 2, 3], [1, 3, 6]]
    active: [[2, 0], [2, 1], [2, 2]]
    note: মানগুলো 1, তারপর 2+1 = 3, তারপর 3+3 = 6। উত্তর 6টি পথ।
```

শেষ ঘরের 6 কোথা থেকে এলো:

```mermaid
flowchart TD
  top["ওপর: dp[1][2] = 3"] -->|নিচে আসা| result["dp[2][2] = 3 + 3 = 6"]
  left["বাঁয়ে: dp[2][1] = 3"] -->|ডানে আসা| result
```

ওপর থেকে আসা পথ আর বাঁ থেকে আসা পথ আলাদা; তাই যোগ করা যায়। যাচাই করার আরেক উপায়: মোট চার move-এ দুইটি right ও দুইটি down। চার জায়গায় দুইটি right বসানোর উপায় `C(4,2)=6`।

## Coin change — আগের amount-এর সেরা উত্তর নাও

Coins `[1,2,5]` দিয়ে amount `11` বানাতে **সর্বনিম্ন কয়টি coin** লাগে? প্রতিটি coin যতবার দরকার ব্যবহার করা যায়। `dp[a]` হলো amount a-এর সর্বনিম্ন coin সংখ্যা।

Base case `dp[0]=0`। যে coin `c ≤ a`, শুধু সেটির জন্য `dp[a−c]+1` candidate। তাই এই উদাহরণে `dp[a] = 1 + min(dp[a−1], dp[a−2], dp[a−5])`, তবে negative index-এর term বাদ দিতে হবে।

```dsa
kind: array
title: Amount হলো index; বাক্সে সর্বনিম্ন coin সংখ্যা
steps:
  - label: শুরু — শুধু amount 0-এর উত্তর জানা
    values: [0, '∞', '∞', '∞', '∞', '∞', '∞', '∞', '∞', '∞', '∞', '∞']
    active: [0]
    note: ∞ মানে এখনো কোনো সমাধান পাওয়া যায়নি।
  - label: Amount 5 পর্যন্ত হিসাব
    values: [0, 1, 1, 2, 2, 1, '∞', '∞', '∞', '∞', '∞', '∞']
    active: [5]
    note: Amount 5-এ একটি 5-coin নিলেই হয়; পাঁচটি 1-coin নেওয়ার দরকার নেই।
  - label: পুরো table — amount 11-এর উত্তর 3
    values: [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]
    active: [11]
    note: একটি সর্বোত্তম সমাধান 5+5+1।
```

প্রতিটি amount-এর হিসাব নিচে আছে। Candidate column-এ coin 1, 2, 5 নেওয়ার **আগের amount-এর** dp value দেখানো হয়েছে; শেষে একটি coin যোগ হয়।

| Amount a | আগের dp values | `1 + min(...)` | একটি সর্বোত্তম বাছাই |
| --- | --- | --- | --- |
| 1 | `dp[0]=0` | 1 | 1 |
| 2 | `dp[1]=1`, `dp[0]=0` | 1 | 2 |
| 3 | `dp[2]=1`, `dp[1]=1` | 2 | 2+1 |
| 4 | `dp[3]=2`, `dp[2]=1` | 2 | 2+2 |
| 5 | `dp[4]=2`, `dp[3]=2`, `dp[0]=0` | 1 | 5 |
| 6 | `dp[5]=1`, `dp[4]=2`, `dp[1]=1` | 2 | 5+1 |
| 7 | `dp[6]=2`, `dp[5]=1`, `dp[2]=1` | 2 | 5+2 |
| 8 | `dp[7]=2`, `dp[6]=2`, `dp[3]=2` | 3 | 5+2+1 |
| 9 | `dp[8]=3`, `dp[7]=2`, `dp[4]=2` | 3 | 5+2+2 |
| 10 | `dp[9]=3`, `dp[8]=3`, `dp[5]=1` | 2 | 5+5 |
| 11 | `dp[10]=2`, `dp[9]=3`, `dp[6]=2` | 3 | 5+5+1 |

Amount 11-এর তিনটি candidate-কে ছবিতে দেখলে:

```mermaid
flowchart TD
  a["dp[10] = 2"] -->|coin 1: মোট 3| result["dp[11] = min(3, 4, 3) = 3"]
  b["dp[9] = 3"] -->|coin 2: মোট 4| result
  c["dp[6] = 2"] -->|coin 5: মোট 3| result
```

শুধু coin সংখ্যা নয়, আসল coin-ও ফেরত পেতে হলে winning choice ধরে পিছিয়ে যাই। Tie হলে যেকোনো সর্বোত্তম choice নেওয়া যায়। এখানে coin 5 আগে বেছে নিচ্ছি:

```mermaid
flowchart LR
  a["amount 11"] -->|নাও 5| b["amount 6"]
  b -->|নাও 5| c["amount 1"]
  c -->|নাও 1| d["amount 0 · শেষ"]
```

জমা coin `5,5,1`; সংখ্যা 3। **DP table সেরা মান রাখে; winning choice-এর পথ আসল সমাধান ফিরিয়ে দেয়।**

## Memoization — একই প্রশ্নের উত্তর আবার হিসাব নয়

সাধারণ recursive `fib(5)`-এ প্রতিটি box একটি function call। একই label একাধিক box-এ আছে, কারণ একই প্রশ্নের উত্তর বারবার হিসাব হচ্ছে। মোট 15টি call।

```mermaid
flowchart TD
  a["fib(5)"] --> b["fib(4)"]
  a --> c["fib(3)"]
  b --> d["fib(3)"]
  b --> e["fib(2)"]
  c --> f["fib(2)"]
  c --> g["fib(1)"]
  d --> h["fib(2)"]
  d --> i["fib(1)"]
  e --> j["fib(1)"]
  e --> k["fib(0)"]
  f --> l["fib(1)"]
  f --> m["fib(0)"]
  h --> n["fib(1)"]
  h --> o["fib(0)"]
```

Memoization-এ প্রথমবার পাওয়া উত্তর cache-এ রাখি; পরের call একই প্রশ্ন করলে সেই উত্তর সরাসরি ফেরত দিই। নিচে বাঁয়ের call আগে চলে এবং **base case-এর উত্তরও cache হয়**। মোট 9টি call; ছয়টি আলাদা value হিসাব হয়, তিনটি cache hit।

```mermaid
flowchart TD
  a["fib(5)"] --> b["fib(4)"]
  a --> c["fib(3) · cache hit"]
  b --> d["fib(3)"]
  b --> e["fib(2) · cache hit"]
  d --> f["fib(2)"]
  d --> g["fib(1) · cache hit"]
  f --> h["fib(1)"]
  f --> i["fib(0)"]
```

Cache hit-এর নিচে আর subtree নেই। বড় n-এ এই ছোট পার্থক্যই বিশাল কাজ বাঁচায়।

| n | সাধারণ recursion-এর call | Memoization-এর call, cache hit-সহ |
| --- | --- | --- |
| 5 | 15 | 9 |
| 10 | 177 | 19 |
| 20 | 21,891 | 39 |
| 50 | 40,730,022,147 | 99 |

এই সাধারণ `fib(n−1)+fib(n−2)` recursion-এ naive call সংখ্যা `2F(n+1)−1`; memoized version-এ `n≥2` হলে `2n−1`। Function call মানেই নতুন state হিসাব নয়—cache hit-ও call হিসেবে গোনা হয়েছে।

## নতুন DP-তে এই পাঁচটি প্রশ্ন করো

1. **State:** প্রতিটি cell ঠিক কোন প্রশ্নের উত্তর রাখে?
2. **Base:** কোন ছোট উত্তরগুলো আগে থেকেই জানা?
3. **Transition:** কোন আগের cell থেকে বর্তমান উত্তর আসবে?
4. **Order:** যাদের উত্তর লাগবে, তারা আগে হিসাব হচ্ছে তো?
5. **Answer:** কোন cell-এ চূড়ান্ত মান, এবং choice ফিরিয়ে আনতে হবে কি?

Code লেখার আগে ছোট input-এ পুরো table ভরো। Grid-এ একটি দেয়াল বসালে base/transition কী বদলায়, অথবা coin 1 বাদ দিলে কোন amount অসম্ভব হয়—এ দুটি পরিবর্তন নিজে trace করলে state-এর অর্থ আরও পরিষ্কার হবে।