# Dynamic Programming — সময়ের মধ্যে শেখার পরিকল্পনা

আপনার একটি target topic order আছে এবং কয়েকটি ছোট lesson আছে। প্রতিটি lesson-এর topic order target-এর সঙ্গে কতটা মেলে, তা LCS দিয়ে score করবেন। তারপর নির্দিষ্ট সময়ের মধ্যে lesson বেছে সেই score-এর যোগফল সর্বোচ্চ করবেন। প্রথম DP-এর result দ্বিতীয় DP-এর value হবে।

**Microsoft কোর্সের সংযোগ:** Module 4-এর dynamic programming ও problem-solving। এখানে state, transition, reconstruction এবং 0/1 choice সরাসরি অনুশীলন হবে।

## ১. আগে পড়া ও অনুশীলনের ক্রম

| ক্রম | উপকরণ | যা বলতে পারবেন |
|---|---|---|
| ১ | [DP ধারণা](../12-dynamic-programming/concept.md), [State-transition thinking](../12-dynamic-programming/state-transition-thinking.md) | State-এর অর্থ, base case, recurrence |
| ২ | [Visual explanation](../12-dynamic-programming/visual-explanation.md), [Fibonacci তিনভাবে](../12-dynamic-programming/problems/001-fibonacci-three-ways.md) | একই subproblem বারবার এলে table কেন |
| ৩ | [Longest Common Subsequence](../12-dynamic-programming/problems/017-longest-common-subsequence.md) | Subsequence বনাম substring, 2D prefix state |
| ৪ | [Book Shop knapsack](../12-dynamic-programming/problems/014-book-shop-knapsack.md) | Take/skip এবং একটি item একবার নেওয়া |
| ৫ | [DP patterns](../12-dynamic-programming/patterns.md) | Table থেকে কোন choice নেওয়া হয়েছিল উদ্ধার করা |

প্রথমে `AC` ও `ABCD`-এর LCS table পূরণ করুন। তারপর দুই lesson-এর ছোট budget table হাতে করুন। Table-এর প্রতিটি ঘরের অর্থ একটি পূর্ণ বাক্যে না বলতে পারলে পরের ধাপে যাবেন না।

## ২. সমস্যা ও scoring rule

`study_plan(lessons, target, budget)` লিখুন। প্রতিটি lesson `(id, minutes, topic_sequence)`। Topic-কে এক অক্ষরের symbol হিসেবে ধরুন: যেমন `A=array`, `B=search`, `C=tree`, `D=graph`। Symbol-এর নির্দিষ্ট mapping আপনার course note-এ লেখা থাকবে; algorithm শুধু symbol মেলে।

1. প্রতিটি lesson-এর sequence ও `target`-এর **LCS length** হলো lesson score। Matched subsequence-টিও report-এ দিন।
2. প্রতিটি lesson সর্বোচ্চ একবার নিন। মোট minutes budget-এর সমান বা কম রেখে score-এর **যোগফল** সর্বোচ্চ করুন।
3. Score সমান হলে DP-এর current lesson skip করুন; অর্থাৎ আগের row-এর plan রাখুন। Minimum minutes আলাদা objective নয়।
4. Chosen ID input order-এ, ব্যবহৃত minutes, সর্বোচ্চ score এবং সব lesson-এর alignment ফেরত দিন।

**Scoring স্পষ্ট করে নিন:** দুটি selected lesson-এ একই topic মিললে সেটি দুবার score পাবে। এটি rehearsal/alignment score, unique topic coverage নয়। Target-এর length `4` হলেও total score `5` হতে পারে। Unique coverage optimize করতে অন্য state লাগবে।

**সীমা:** `0 ≤ lesson_count ≤ 80`, `0 ≤ budget ≤ 2,000`, positive integer minutes, প্রতিটি sequence ও target সর্বোচ্চ `100` symbol; ID আলাদা string। Negative budget, nonpositive duration বা duplicate ID-তে `ValueError`। Empty target/lesson sequence বৈধ; তখন সংশ্লিষ্ট score `0`। Input অপরিবর্তিত রাখুন।

```python
study_plan(
    [("A", 3, "AC"), ("B", 4, "ABD"), ("C", 2, "BC")],
    target="ABCD",
    budget=6,
)
```

| Lesson | Minutes | Matched topics | Score |
|---|---:|---|---:|
| A | 3 | `AC` | 2 |
| B | 4 | `ABD` | 3 |
| C | 2 | `BC` | 2 |

`A+B`-এর সময় `7`, তাই নেওয়া যায় না। `A+C`-তে score `4`, সময় `5`। `B+C`-তে score `5`, সময় `6`; এটিই উত্তর। B topic দুই lesson-এ গণনা হয়েছে।

```python
{
    "chosen": ["B", "C"], "minutes": 6, "score": 5,
    "alignment": [
        {"id": "A", "matched": "AC", "score": 2},
        {"id": "B", "matched": "ABD", "score": 3},
        {"id": "C", "matched": "BC", "score": 2},
    ],
}
```

```mermaid
flowchart LR
    seq["Lesson sequence + target"] --> lcs["LCS table\nscore ও matched topics"]
    lcs --> items["minutes, score item"]
    items --> pack["0/1 knapsack\ntake অথবা skip"]
    pack --> trace["Table ধরে পেছনে হাঁটা"]
    trace --> report["Chosen ID, minutes, score"]
```

## ৩. চার ধাপের guided problem

### A — LCS state ও transition

`lcs[i][j]` হবে lesson-এর প্রথম `i` symbol ও target-এর প্রথম `j` symbol-এর LCS length। একটি prefix খালি হলে উত্তর `0`। শেষ symbol মিললে diagonal+1; না মিললে ওপর/বামের maximum।

**Invariant:** `lcs[i][j]` পড়ার সময় তার দরকারি ছোট prefix state তৈরি আছে। **Checkpoint:** `AC` ও `ABCD`-এর final score `2`; `AB` ও `BA`-এর score `1`, `2` নয়।

### B — Matched sequence উদ্ধার

শেষ cell থেকে পেছনে হাঁটুন। Symbol মিললে সেটি সংগ্রহ করে diagonal-এ যান। না মিললে বড় neighbor-এর দিকে যান; সমান হলে ওপরের cell নিন। শেষে collected symbol reverse করুন।

**Checkpoint:** Recovered sequence দুই input-এরই subsequence হতে হবে এবং length table-এর score-এর সমান। একাধিক LCS হলে যেকোনো valid witness ঠিক; reference-এর ওপর-আগে tie rule deterministic ফল দেয়।

### C — Lesson নির্বাচন

`best[i][b]` মানে প্রথম `i` lesson-এর মধ্যে budget `b`-তে সর্বোচ্চ score। Skip: `best[i-1][b]`। Take সম্ভব হলে: `score[i-1] + best[i-1][b-minutes[i-1]]`।

**Invariant:** Take-এর পরে **আগের row** পড়বেন; বর্তমান row পড়লে একই lesson বারবার নেওয়া হয়ে যেতে পারে। **Checkpoint:** একটি ২-minute, ২-score lesson আর budget `20` হলেও answer `2`, `20` নয়।

### D — Plan reconstruction ও final audit

`best[n][budget]` থেকে আগের row-এর সঙ্গে তুলনা করুন। সমান হলে skip। আলাদা হলে current lesson নেওয়া হয়েছে; budget থেকে তার minutes বাদ দিয়ে আগের row-এ যান। Chosen list reverse করুন।

**Checkpoint:** example-এ C নেওয়ার পরে remaining budget `4`; B নিলে `0`। Chosen lesson-এর duration sum `6`, alignment score sum `5`। এই দুটি report-এর সংখ্যার সঙ্গে মিলতে হবে।

## ৪. সমাধান বুঝে মিলিয়ে দেখুন

??? success "দুটি DP-এর correctness"

    LCS-এর শেষ symbol মিললে তাকে শেষ match ধরে ছোট prefix-এর optimal answer বাড়ানো যায়; না মিললে অন্তত এক পাশের শেষ symbol বাদ যাবে। দুই choice-এর maximum-ই উত্তর।

    Knapsack-এ প্রতিটি plan-এর শেষ lesson হয় নেওয়া হয়েছে, নয়তো হয়নি। এই দুই ভাগ সব valid plan cover করে; আগের row ব্যবহারে একটি lesson একবারের বেশি নেওয়া যায় না। প্রথম DP-এর score দ্বিতীয় DP-তে value হিসেবে যায়, তাই দুই কাজ বিচ্ছিন্ন exercise নয়।

    [Python solution](../practice/dynamic_programming_lab.py){ download } · [unit test](../practice/test_dynamic_programming_lab.py){ download }।

## ৫. Test ও complexity

Repository root থেকে; download করলে দুই ফাইল `practice/`-এ রেখে:

```bash
python -m unittest discover -s practice -p 'test_dynamic_programming_lab.py' -v
```

৮টি test method example, empty/zero case, unrelated topics, item reuse, tie rule, repeated symbol ও invalid input দেখে। ৭০টি seeded ছোট case-এ LCS সব subsequence enumerate করে এবং lesson selection সব subset enumerate করে যাচাই হয়। Chosen plan-এর score, duration ও uniqueness-ও পরীক্ষা হয়।

`N` lesson, `B` budget, target length `T`, lesson length `Lᵢ` হলে time `O(T × ΣLᵢ + NB)`। LCS table একবারে একটি lesson-এর জন্য থাকে; knapsack reconstruction-এর table-সহ space `O(T × max Lᵢ + NB)` এবং report storage। Table কমিয়ে one-dimensional করলে reconstruction-এর জন্য অতিরিক্ত পরিকল্পনা দরকার।

## ৬. Coverage ও বাকি অনুশীলন

| এখানে শিখলেন | আলাদা করে করবেন |
|---|---|
| Prefix-based 2D DP ও LCS | [Edit distance](../12-dynamic-programming/problems/018-edit-distance.md) |
| 0/1 take-skip, budget state | [Coin combinations](../12-dynamic-programming/problems/012-coin-combinations-i.md)-এ reuse ও counting |
| Optimal value থেকে solution উদ্ধার | [LIS](../12-dynamic-programming/problems/015-lis-n-squared.md) |
| Base case, transition, tie rule | [Grid paths](../12-dynamic-programming/problems/008-grid-paths-with-traps.md), interval DP |

একটি capstone-এ DP-এর সব state shape নেই। [সব DP problem](../12-dynamic-programming/problems/README.md) থেকে remaining pattern করুন।