# DP: একই ছোট প্রশ্নের উত্তর পুনরায় ব্যবহার

[অধ্যায়ের সূচি](README.md) · [অনুশীলন ও সমাধান](problems/README.md) · [মূল ধারণা](concept.md)

DP-তে table আঁকার আগে একটি বাক্য লিখুন: **এই cell কী প্রশ্নের উত্তর?** `dp[i]` কখনো প্রথম iটি item-এর উত্তর, কখনো ঠিক i-তে শেষ হওয়া উত্তরের মান। এই দুই অর্থ মিশে গেলে code দেখতে ঠিক হলেও ফল ভুল হবে।

## শেখার ক্রম

| ধাপ | পড়া | লক্ষ্য |
| --- | --- | --- |
| 1 | [Repeated subproblem ও memoization](concept.md) | কোন প্রশ্ন বারবার হচ্ছে তা খুঁজে পাওয়া |
| 2 | [Table-এর প্রতিটি ধাপ](visual-explanation.md) | Known cell থেকে next cell হিসাব |
| 3 | [State → transition → base → order → answer](state-transition-thinking.md) | Code-এর আগে পাঁচটি বাক্য লেখা |
| 4 | [Pattern-এর তুলনা](patterns.md) | Counting, minimum, boolean আলাদা করা |
| 5 | [Implementation](implementation.py) ও [problem tracker](problems/README.md) | নিজের trace-এর সঙ্গে output মেলানো |

## একটি প্রোগ্রাম: নির্দিষ্ট দৈর্ঘ্যের জন্য কম প্যাকেট

ধরি একটি delivery service-এ 1, 3 ও 4 ইউনিটের packet আছে; প্রত্যেকটি যতবার খুশি নেওয়া যায়। মোট 6 ইউনিট পাঠাতে সর্বনিম্ন কয়টি packet লাগবে? বড়টি আগে নিলে 4+1+1 = 3টি। কিন্তু 3+3 = 2টি। তাই এই denomination-এ greedy যথেষ্ট নয়।

**State:** `dp[s]` = ঠিক s ইউনিট বানাতে সর্বনিম্ন packet। **Base:** `dp[0]=0`। **Transition:** শেষ packet c হলে বাকি `s-c`; তাই `dp[s]=1+min(dp[s-c])`, কেবল `c<=s` বিবেচনা করুন।

| s | শেষ 1 | শেষ 3 | শেষ 4 | dp[s] | একটি পছন্দ |
| --- | --- | --- | --- | --- | --- |
| 0 | — | — | — | 0 | খালি |
| 1 | 1+dp[0]=1 | — | — | 1 | [1] |
| 2 | 1+dp[1]=2 | — | — | 2 | [1,1] |
| 3 | 1+dp[2]=3 | 1+dp[0]=1 | — | 1 | [3] |
| 4 | 1+dp[3]=2 | 1+dp[1]=2 | 1+dp[0]=1 | 1 | [4] |
| 5 | 1+dp[4]=2 | 1+dp[2]=3 | 1+dp[1]=2 | 2 | [4,1] |
| 6 | 1+dp[5]=3 | 1+dp[3]=2 | 1+dp[2]=3 | 2 | [3,3] |

```mermaid
flowchart LR
  zero["dp[0] = 0"] -->|"শেষ packet 3"| three["dp[3] = 1"]
  three -->|"শেষ packet 3"| six["dp[6] = 2"]
  two["dp[2] = 2"] -->|"শেষ packet 4: মোট 3"| six
  five["dp[5] = 2"] -->|"শেষ packet 1: মোট 3"| six
```

প্রতিটি dependency ছোট sum-এর দিকে, তাই `s=1` থেকে 6 ক্রমে table ভরা যায়। `amount=A`, coin type `k` হলে সময় `O(Ak)`, space `O(A)`। এই সীমা amount-এর উপর নির্ভর করে; A অনেক বড় হলে শুধু coin type কম বলে code দ্রুত হবে না।

## একই data, ভিন্ন প্রশ্ন

| প্রশ্ন | State-এর মান | একাধিক choice মিলবে কীভাবে | Base |
| --- | --- | --- | --- |
| সর্বনিম্ন coin কত | সংখ্যা বা infinity | min | dp[0]=0 |
| কোনো subset দিয়ে sum হয় কি | True/False | OR | dp[0]=True |
| Ordered sequence কতটি | count | যোগ | dp[0]=1 |
| সর্বোচ্চ লাভ কত | best value | max | খালি নির্বাচন বৈধ হলে 0 |

Coin `[2,3,5]` দিয়ে sum 5-এর ordered sequence `[2,3]`, `[3,2]`, `[5]`: মোট **3**। [Coin Combinations I-এর সম্পূর্ণ table](problems/012-coin-combinations-i.md) দেখুন। Counting-এ `dp[0]=1` মানে একটি খালি sequence; এটি সব প্রথম coin যোগ করার ভিত্তি।

## Loop-এর দিক কেন অর্থ বদলায়

একটি item একবারই নেওয়া গেলে 1D knapsack-এ capacity **বড় থেকে ছোট** ঘুরুন। নইলে এই item দিয়ে আপডেট হওয়া ছোট capacity পড়ে একই item দ্বিতীয়বার ব্যবহার হয়ে যেতে পারে। একই coin বারবার নেওয়া বৈধ হলে এই পুনর্ব্যবহারই দরকার।

বাস্তব প্রয়োগে [Edit Distance](problems/018-edit-distance.md) string-এর মিল মাপে, [Book Shop](problems/014-book-shop-knapsack.md) budget-এর মধ্যে selection শেখায়, আর [DAG-এর longest path](problems/023-longest-path-dag.md) dependency-ভিত্তিক কাজের পরিকল্পনার ভিত্তি। প্রতিটি ক্ষেত্রে আগে state-এর অর্থ ও constraints লিখুন।