# DP Patterns — The Named Families

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

> DP problem অসীম নয়। বেশিরভাগই হাতে-গোনা কয়েকটা family-র সদস্য — প্রত্যেকটার নিজস্ব trigger word, state-এর আকার আর transition-এর আকার আছে। Family-গুলো শিখে নাও, তাহলে "এটা কোন DP?" হয়ে যায় একটা lookup, আন্দাজ নয়।

নিচের প্রতিটা family-র জন্য: কীভাবে *চিনবে*, state দেখতে কেমন, transition দেখতে কেমন, আর practice কোথায়।

---

## 1. 1D linear DP

- **Trigger words:** "n steps / days / houses in a row", "count the ways to reach", "max value up to position i", একটা sequence, decision-গুলো বাঁ থেকে ডানে নেওয়া।
- **State shape:** `dp[i]` = `i`-তে শেষ হওয়া (বা length `i`-এর) prefix-এর উত্তর।
- **Transition shape:** `dp[i] = combine(dp[i-1], dp[i-2], ...)` — fixed, ছোট একটা look-back।
- **Representative problems:**
  - [Climbing Stairs (LeetCode 70)](https://leetcode.com/problems/climbing-stairs/)
  - [House Robber (LeetCode 198)](https://leetcode.com/problems/house-robber/)
  - [Maximum Subarray (LeetCode 53)](https://leetcode.com/problems/maximum-subarray/) — Kadane আসলে `dp[i] = max(a[i], dp[i-1] + a[i])`
  - [Dice Combinations (CSES 1633)](https://cses.fi/problemset/task/1633)

## 2. Grid DP

- **Trigger words:** "grid / matrix / lattice", "move only right and down", "minimum path cost", "count paths", "obstacles"।
- **State shape:** `dp[r][c]` = cell `(r, c)`-তে পৌঁছানোর উত্তর।
- **Transition shape:** `dp[r][c] = combine(dp[r-1][c], dp[r][c-1])` — allowed move-গুলোই neighbor ঠিক করে দেয়।
- **Representative problems:**
  - [Unique Paths (LeetCode 62)](https://leetcode.com/problems/unique-paths/)
  - [Grid Paths with traps (CSES 1638)](https://cses.fi/problemset/task/1638)
  - [Minimum Path Sum (LeetCode 64)](https://leetcode.com/problems/minimum-path-sum/)

## 3. Knapsack family

এক skeleton ভাগ করে নেওয়া তিন ভাইবোন — `dp[budget]` বা `dp[item][budget]` — পার্থক্য শুধু *একটা item কতবার ব্যবহার করা যায়* আর *প্রশ্নটা কী*।

### 3a. 0/1 knapsack (প্রতিটা item সর্বোচ্চ একবার)

- **Trigger words:** "each item once", "choose a subset", weights + values + capacity।
- **State shape:** `dp[i][w]` = প্রথম `i`-টা item দিয়ে weight `w`-এর মধ্যে best value (1D-তে compress হয়, ভরতে হয় **ডান থেকে বাঁয়ে**)।
- **Transition shape:** `dp[i][w] = max(dp[i-1][w], dp[i-1][w - wt[i]] + val[i])` — নাও বা রেখে দাও।
- **Representative problems:**
  - [Book Shop (CSES 1158)](https://cses.fi/problemset/task/1158)

### 3b. Unbounded knapsack (item reusable)

- **Trigger words:** "unlimited supply", "coins", "as many times as you like"।
- **State shape:** `dp[a]` = budget/amount `a`-র উত্তর (1D, ভরা হয় **বাঁ থেকে ডানে** — ওই direction-টাই reuse-এর অনুমতি দেয়)।
- **Transition shape:** `dp[a] = best over coins c of f(dp[a - c])`।
- **Representative problems:**
  - [Coin Change (LeetCode 322)](https://leetcode.com/problems/coin-change/), [Minimizing Coins (CSES 1634)](https://cses.fi/problemset/task/1634) — count minimize করো
  - [Coin Combinations I (CSES 1635)](https://cses.fi/problemset/task/1635) — ordered ways গোনো

### 3c. Subset-sum (feasibility flavor)

- **Trigger words:** "can the array be split", "is there a subset summing to T", "two piles as equal as possible"।
- **State shape:** `dp[s]` = True/False — sum `s` কি reachable? (Value-র বদলে boolean; বাকিটা খাঁটি 0/1 mechanics।)
- **Transition shape:** প্রতিটা element `x`-এর জন্য `dp[s] |= dp[s - x]`, `s` sweep হয় ডান থেকে বাঁয়ে।
- **Representative problems:**
  - [Partition Equal Subset Sum (LeetCode 416)](https://leetcode.com/problems/partition-equal-subset-sum/)

## 4. LIS family

- **Trigger words:** "longest increasing", "longest chain", "maximum number that can be nested / stacked", envelopes, boxes, দুটো attribute দিয়ে sort করা team।
- **State shape:** `dp[i]` = **ঠিক i-তে শেষ হওয়া** subsequence-এর best উত্তর (এই anchor-টাই family-র signature)।
- **Transition shape:** `a[j] < a[i]` এমন সব `j < i`-এর উপর `dp[i] = 1 + max(dp[j])` — একটা *খোঁজাখুঁজি করা* look-back, প্রতি state-এ O(n), family 1-এর fixed look-back-এর মতো নয়। (Speed-up: binary search দিয়ে O(n log n), বা value-গুলোর উপর একটা Fenwick tree — folder 11।)
- **Representative problems:**
  - [Longest Increasing Subsequence (LeetCode 300)](https://leetcode.com/problems/longest-increasing-subsequence/)
  - Envelope/box nesting variant-গুলো — এক dimension sort করো, অন্যটার LIS নাও।

## 5. String DP (two-sequence alignment)

- **Trigger words:** "two strings", "edit / transform / align", "common subsequence", "delete to make equal", "wildcard matching"।
- **State shape:** `dp[i][j]` = `a`-র প্রথম `i`-টা char-কে `b`-র প্রথম `j`-টা char-এর সাথে তুলনার উত্তর।
- **Transition shape:** `a[i-1] == b[j-1]` কি না — তার উপর case-split; হাত যায় `dp[i-1][j-1]`, `dp[i-1][j]`, `dp[i][j-1]`-এ।
- **Representative problems:**
  - [Longest Common Subsequence (LeetCode 1143)](https://leetcode.com/problems/longest-common-subsequence/)
  - [Edit Distance (LeetCode 72)](https://leetcode.com/problems/edit-distance/)
  - [Word Break (LeetCode 139)](https://leetcode.com/problems/word-break/) — একটা string বনাম একটা dictionary; 1D state `dp[i]` = "length i-এর prefix segmentable", একই prefix-চেতনা।

## 6. Interval DP (teaser)

- **Trigger words:** "merge adjacent piles", "burst / remove items where cost depends on neighbors", "best way to fully process a range", matrix-chain-ধাঁচের grouping।
- **State shape:** `dp[l][r]` = subarray `l..r`-এর best উত্তর — state-গুলো *interval*, prefix নয়।
- **Transition shape:** Interval-এর ভেতরের প্রতিটা split point বা প্রতিটা "last element processed" `k` try করো: `dp[l][r] = best over k of dp[l][k] ⊕ dp[k][r] ⊕ cost(l, k, r)`। Fill order: interval-এর **length** বাড়ার ক্রমে — ছোট interval আগে, তাদের ধারণ করা বড়গুলো পরে।
- **Representative problem:** [Burst Balloons (LeetCode 312)](https://leetcode.com/problems/burst-balloons/) — classic সেই উল্টোচিন্তা: "প্রথম নয়, LAST balloon-টা কোনটা ফাটল, সেটা ভাবো"।
- শুধুই teaser: আগে family 1–5 master করো; interval DP তার নিজের deep dive পরে পাবে।

## 7. Bitmask DP (teaser)

- **Trigger words:** "n ≤ ~20", "visit every city / use every element exactly once", "assign tasks to people", যখনই state-কে মনে রাখতে হয় *কোন subset* ব্যবহৃত হয়েছে।
- **State shape:** `dp[mask]` (প্রায়ই `dp[mask][last]`), যেখানে `mask` একটা integer যার bit-গুলো used element mark করে — subset-টাই *state*, আর সেটা affordable শুধু এজন্যই যে 2^20 ≈ 10^6।
- **Transition shape:** Mask-টাকে একটা unused element দিয়ে বাড়াও: প্রতিটা unset bit `j`-এর জন্য `dp[mask | (1 << j)] = best(dp[mask] + cost(...))`।
- **Representative idea:** traveling-salesman-ধাঁচের "visit all, minimize cost" task।
- Bit trick-গুলো (`mask & (1 << j)`, set bit iterate করা) আসে math level 4 (bit manipulation) থেকে, আর combinatorial subset-enumeration idea-গুলো math level 11 থেকে — চেষ্টার আগে দুটোই ঝালিয়ে নাও।

## 8. DP on DAG

- **Trigger words:** "dependencies", "course prerequisites", "longest path in a DAG", "count paths from s to t in a directed acyclic graph"।
- **State shape:** `dp[v]` = vertex `v`-এর উত্তর।
- **Transition shape:** `dp[v] = combine(dp[u] for each edge u -> v)` — process হয় **topological order**-এ, যেটা ঠিক সেই ভূমিকাটাই পালন করে table DP-তে "fill order" যা করে। আসলে *প্রতিটা* DP-ই গোপনে state-গুলোর একটা DAG; topological sort সেটাকে explicit করে দেয়।
- **Ordering-টা কোথায় শিখবে:** [../09-graphs/topological-sort.md](../09-graphs/topological-sort.md)।
- **Representative tasks:** DAG-এ longest path, DAG-এ path গোনা — graph + DP combo-টা দেখো [../13-interview-master-problems/hard-patterns.md](../13-interview-master-problems/hard-patterns.md)-এ।

---

## The family-spotting table

| You read... | Suspect family | State sketch |
| --- | --- | --- |
| "ways to reach step/day n" | 1D linear | `dp[i]` |
| "grid, move right/down" | Grid | `dp[r][c]` |
| "items once, capacity" | 0/1 knapsack | `dp[i][w]` |
| "coins, unlimited" | Unbounded knapsack | `dp[a]` |
| "split into equal halves?" | Subset-sum | `dp[s]` bool |
| "longest increasing / nesting" | LIS | `dp[i]` ends-at-i |
| "two strings, transform/compare" | String DP | `dp[i][j]` |
| "merge/burst a range, cost from neighbors" | Interval | `dp[l][r]` |
| "n ≤ 20, use each exactly once" | Bitmask | `dp[mask]` |
| "prerequisites / DAG, longest chain" | DP on DAG | `dp[v]` topo order |

## How to use this file (এই file কীভাবে ব্যবহার করবে)

1. নতুন problem পড়ো; trigger word-গুলোর নিচে দাগ দাও।
2. Table-এর সাথে মেলাও; সন্দেহভাজন state shape-টা লেখো।
3. [state-transition-thinking.md](state-transition-thinking.md)-এর পুরো 5-step doctrine চালাও — family তোমাকে step 1-এ একটা head start দেয়, step 2–5-এর replacement কখনোই নয়।
4. কোনো family না মিললে সেটাও information: state-টার হয়তো একটা creative anchor লাগবে (LIS-এর শিক্ষা) বা একটা extra dimension।

আরও pattern-চর্চা: USACO Guide-এর DP module ([usaco.guide/gold/intro-dp](https://usaco.guide/gold/intro-dp)) contest DP-কে প্রায় একই family-রেখায় সাজিয়েছে।