# 12 — Dynamic Programming

> **এখান থেকে শুরু করুন:** [সহজ ব্যাখ্যা, শেখার ক্রম ও বাস্তব ব্যবহার](learning-guide.md) → [প্রশ্ন, official link ও স্থানীয় সমাধান](problems/README.md)। [উৎসের তালিকা](source-map.md)-এ reference পাবেন।

> Smart recursion, যে কোনোদিন একই প্রশ্নের উত্তর দুবার দেয় না। Recursion তো তুমি জানোই — DP মানে recursion plus একটা খাতা।

---

## What is this technique (এই technique-টা কী)

**Dynamic programming (DP)** এমন problem solve করার একটা উপায়, যেগুলো *overlapping* subproblem-এ ভাঙে। সাধারণ recursion একই subproblem লক্ষ লক্ষ বার solve করে; DP প্রতিটা subproblem **একবার** solve করে, উত্তরটা লিখে রাখে, আর তারপর চিরকাল reuse করে।

DP সরাসরি উত্তরাধিকার পায় তোমার জানা জিনিসগুলো থেকে:

- **recursion** ([../06-recursion-and-backtracking/](../06-recursion-and-backtracking/README.md)) — একটা problem-কে তার নিজের ছোট ছোট version-এ ভাঙো,
- **repeated subproblem-এর observation** — একই recursive call বারবার ফিরে আসে,
- **state thinking** — "problem-এর ভেতরে আমি কোথায় আছি"-টাকে কয়েকটা সংখ্যায় প্রকাশ করা।

নতুন **thinking tweak**-টা একটাই: কোনো code লেখার আগে, সাদা ভাষায় **STATE**-টা define করো — "`dp[i]` মানে ___" — তারপর জিজ্ঞেস করো, ছোট state থেকে একটা state কীভাবে তৈরি হয় (এটাই **transition**)। State ঠিক হলে code নিজেই লিখে যায়। State ভুল হলে কোনো পরিমাণ code-ই বাঁচাতে পারবে না।

আর সবচেয়ে নরম on-ramp: **memoization মানে শুধু recursion + একটা খাতা।** যে recursive function এমনিতেই লিখতে, সেটাই, plus একটা dictionary যে উত্তর মনে রাখে।

## Why it exists (কোন ব্যথাটা সারায়)

`fib(50)`-এর উপর naive recursion প্রায় 40 billion call করে, কারণ `fib(48)`, `fib(47)`, ... প্রত্যেকটা astronomically অনেকবার আবার computed হয়। Recursion-টা *সঠিক* — সে শুধু অপচয়ী রকমের ভুলোমনা।

DP ঠিক ওই অপচয়টাই সারায়:

| Approach | fib(50) cost | কেন |
| --- | --- | --- |
| Naive recursion | ~2^50 calls | সবকিছু আবার solve করে, exponential |
| Memoized recursion | 51 distinct calls | প্রতিটা subproblem একবার solved |
| Tabulation (loop) | 51 loop steps | একই, recursion-এর overhead ছাড়া |

DP যে ব্যথাটা সরায় তা হলো **repetition-এর কারণে exponential blow-up** — "মহাবিশ্ব শেষ হওয়ার আগে impossible"-কে বানিয়ে দেয় "milliseconds"।

## Where it is used (কোথায় ব্যবহার হয়)

- Shortest paths আর routing-এ (Bellman-Ford, Floyd-Warshall আসলে DP)।
- Spell-check আর diff tool-এ (edit distance, longest common subsequence)।
- Bioinformatics-এ: DNA sequence alignment হলো বিশাল scale-এ string DP।
- Resource allocation আর scheduling-এ (knapsack-family problems)।
- Compiler-এ (optimal instruction selection), text justification-এ, regex engine-এ।
- Reinforcement learning-এ: value iteration হলো environment-এর state-গুলোর উপর DP।
- Medium/hard interview question-এর মোটামুটি এক-তৃতীয়াংশে।

## Prerequisites

- পাকা recursion: base case, recursive case, recursive call-কে বিশ্বাস করা ([../06-recursion-and-backtracking/](../06-recursion-and-backtracking/README.md))।
- Array আর 2D list ([../02-arrays-and-strings/](../02-arrays-and-strings/README.md))।
- Memo table-এর জন্য hash map ([../05-hashing/](../05-hashing/README.md))।
- "States সংখ্যা × প্রতি state-এর কাজ" — এই level-এর Big-O।

## What to revise before learning (শেখার আগে কী ঝালাই করবে)

- `fib`-কে recursively লেখা আর তার call tree হাতে trace করা।
- Python dictionary: `if key in memo`, `memo[key] = value`।
- Nested loop দিয়ে একটা 2D grid row by row ভরা।
- "Trust the recursive call" — কথাটা; DP-ও একই বিশ্বাসের লাফ চায়।

## Learning goals (checklist)

- [ ] fib(5)-এর call tree আঁকো আর প্রতিটা repeated call-এ গোল দাও।
- [ ] DP-র দুটো requirement বলো: overlapping subproblems + optimal substructure।
- [ ] একটা recursive solution-কে ~4 লাইন যোগ করে memoized top-down বানাও।
- [ ] একই solution-কে bottom-up tabulation-এ convert করো।
- [ ] 5-step doctrine মুখস্থ বলো: state, transition, base cases, fill order, answer location।
- [ ] এগুলোর জন্য এক বাক্যে state define করো: stairs, robber, coins, grid, LIS, knapsack।
- [ ] একটা ছোট DP table পুরোটা হাতে ভরো, code না চালিয়ে।
- [ ] Complexity estimate করো (number of states) × (work per transition) হিসেবে।
- [ ] Knapsack family vs LIS family vs string DP — দেখামাত্র চেনো।
- [ ] Coins [1, 3, 4] আর amount 6-এ greedy কেন fail করে, ব্যাখ্যা করো।

## Problem categories

| Category | Typical question shape |
| --- | --- |
| 1D linear DP | "Position i-তে পৌঁছানোর ways গোনো / best value বের করো" |
| Grid DP | "Right/down চলে grid-এর ভেতর path বা min cost" |
| Knapsack family | "Budget-এর মধ্যে item বাছো", "কোনো subset-এর sum কি X হতে পারে" |
| Unbounded knapsack | "Coin / item যতবার খুশি reuse করা যায়" |
| LIS family | "Longest increasing / একটার ভেতর আরেকটা ঢোকে এমন chain" |
| String DP | "দুটো string-এর তুলনা: LCS, edit distance, alignment" |
| Interval DP | "একটা range-কে split / merge করার best উপায়" |
| Bitmask DP | "ছোট n, subset-গুলোই state" |
| DP on DAG | "Dependency graph-এ longest path / path গোনা" |

## Practice list

নিচের problem statement-গুলো নিজেদের ভাষায় বর্ণনা করা; official statement-এর জন্য link-এ যাও।

### Easy

| Problem | Source | Pattern |
| --- | --- | --- |
| Climbing Stairs — 1 বা 2 ধাপ করে n সিঁড়ি ওঠার ways গোনো · [ব্যাখ্যা](problems/002-climbing-stairs.md) | [LeetCode 70](https://leetcode.com/problems/climbing-stairs/) | 1D linear DP |
| Fibonacci Number — memoization-এর hello-world · [ব্যাখ্যা](problems/001-fibonacci-three-ways.md) | [LeetCode 509](https://leetcode.com/problems/fibonacci-number/) | 1D linear DP |
| Min Cost Climbing Stairs — সবচেয়ে সস্তায় চূড়ায় ওঠো · [ব্যাখ্যা](problems/003-min-cost-climbing-stairs.md) | [LeetCode 746](https://leetcode.com/problems/min-cost-climbing-stairs/) | 1D linear DP |
| Dice Combinations — dice roll দিয়ে sum n বানানোর ways গোনো · [ব্যাখ্যা](problems/004-dice-combinations.md) | [CSES 1633](https://cses.fi/problemset/task/1633) | 1D counting DP |
| Maximum Subarray — best contiguous sum (Kadane আসলে ছদ্মবেশী DP) · [ব্যাখ্যা](problems/005-maximum-subarray-as-dp.md) | [LeetCode 53](https://leetcode.com/problems/maximum-subarray/) | 1D linear DP |

### Medium

| Problem | Source | Pattern |
| --- | --- | --- |
| House Robber — max লুট, পাশাপাশি দুটো বাড়ি নয় · [ব্যাখ্যা](problems/006-house-robber.md) | [LeetCode 198](https://leetcode.com/problems/house-robber/) | 1D take-or-skip |
| Coin Change — একটা amount বানাতে সবচেয়ে কম coin · [ব্যাখ্যা](problems/010-coin-change-min.md) | [LeetCode 322](https://leetcode.com/problems/coin-change/) | Unbounded knapsack (min) |
| Minimizing Coins — একই task, contest flavor · [ব্যাখ্যা](problems/011-minimizing-coins.md) | [CSES 1634](https://cses.fi/problemset/task/1634) | Unbounded knapsack (min) |
| Coin Combinations I — একটা sum বানানোর ordered ways গোনো · [ব্যাখ্যা](problems/012-coin-combinations-i.md) | [CSES 1635](https://cses.fi/problemset/task/1635) | Unbounded counting |
| Unique Paths — m×n grid-এ lattice path গোনো · [ব্যাখ্যা](problems/007-unique-paths.md) | [LeetCode 62](https://leetcode.com/problems/unique-paths/) | Grid DP |
| Grid Paths — blocked cell-ওয়ালা grid-এ path গোনো · [ব্যাখ্যা](problems/008-grid-paths-with-traps.md) | [CSES 1638](https://cses.fi/problemset/task/1638) | Grid DP with obstacles |
| Longest Increasing Subsequence · [ব্যাখ্যা](problems/015-lis-n-squared.md) | [LeetCode 300](https://leetcode.com/problems/longest-increasing-subsequence/) | LIS family |
| Partition Equal Subset Sum — array-টাকে দুটো সমান-sum ভাগে ভাঙা যায়? · [ব্যাখ্যা](problems/013-partition-equal-subset-sum.md) | [LeetCode 416](https://leetcode.com/problems/partition-equal-subset-sum/) | 0/1 knapsack (subset sum) |
| Word Break — string-টাকে কি dictionary-র শব্দে কাটা যায়? · [ব্যাখ্যা](problems/016-word-break.md) | [LeetCode 139](https://leetcode.com/problems/word-break/) | 1D DP over prefixes |
| Longest Common Subsequence · [ব্যাখ্যা](problems/017-longest-common-subsequence.md) | [LeetCode 1143](https://leetcode.com/problems/longest-common-subsequence/) | String DP |
| Book Shop — দাম আর page count-সহ classic 0/1 knapsack · [ব্যাখ্যা](problems/014-book-shop-knapsack.md) | [CSES 1158](https://cses.fi/problemset/task/1158) | 0/1 knapsack |

### Hard

| Problem | Source | Pattern |
| --- | --- | --- |
| Edit Distance — এক string থেকে আরেকটায় যেতে min insert/delete/replace · [ব্যাখ্যা](problems/018-edit-distance.md) | [LeetCode 72](https://leetcode.com/problems/edit-distance/) | String DP |
| Longest Increasing Subsequence in O(n log n) — LC 300 আবার করো, patience sorting দিয়ে · [ব্যাখ্যা](problems/015-lis-n-squared.md) | [LeetCode 300](https://leetcode.com/problems/longest-increasing-subsequence/) | LIS + binary search |
| Burst Balloons — balloon ফাটানোর order ঠিক করে coin maximize করো · [ব্যাখ্যা](problems/021-burst-balloons.md) | [LeetCode 312](https://leetcode.com/problems/burst-balloons/) | Interval DP |
| Regular Expression Matching — `.` আর `*` matching implement করো · [ব্যাখ্যা](problems/022-regex-matching.md) | [LeetCode 10](https://leetcode.com/problems/regular-expression-matching/) | String DP, hard transitions |
| Codeforces থেকে চোখ বুজে বাছা যেকোনো 1400–1700 rated DP problem · [ব্যাখ্যা](problems/024-codeforces-blind-pick.md) | [Codeforces problemset](https://codeforces.com/problemset/) | Pattern recognition |

## Visualization ideas

- fib(5)-এর call tree আঁকো, তারপর memoization-এর পরে আবার আঁকো — পুরো পুরো branch উধাও হয়ে যেতে দেখো।
- একটা grid-paths table পেন্সিল দিয়ে cell by cell ভরো; প্রতিটা cell আক্ষরিকভাবে top + left।
- Coin change-এর জন্য, amount 0..11 একটা number line-এ আঁকো আর 1, 2, 5 length-এর arrow পেছনে লাফাতে দাও।
- LIS-এর জন্য, array-টাকে উচ্চতায় বসানো dot হিসেবে আঁকো, আর subsequence-টাকে উঠতে থাকা সিঁড়ি হিসেবে।
- Knapsack: একটা 2D table, যেখানে প্রতিটা row "আরও একটা item বিবেচনা করে" — item নেওয়া হলে shade দাও।

## Common mistakes (সাধারণ ভুল)

- State-টা শব্দে define করার আগেই code করা — unfixable DP bug-এর #1 কারণ।
- Information missing থাকা state (যেমন robber DP-তে "আগের বাড়িটা লুট করেছি কি না" fold করা নেই)।
- ভুল fill order: `dp[i - 1]` লেখা হওয়ার আগেই পড়ে ফেলা।
- "Count the ways" আর "find the best" গুলিয়ে ফেলা — skeleton এক, combine আলাদা (`+` vs `min`/`max`)।
- Base case ভুলে যাওয়া, বা `dp[0]`-কে ভুল identity দেওয়া (0 vs 1 vs infinity)।
- Memoization-এ list-কে dict key বানানো (unhashable) — tuple-এ convert করো।
- Greedy কাজ করবে ধরে নেওয়া: coins [1, 3, 4], amount 6 — greedy বলে 4+1+1 (3 coins), DP বলে 3+3 (2 coins)।
- Index-এর "i-th element" আর "first i elements" interpretation-এর মধ্যে off-by-one।

## Connection to interview problems

Big-tech-ধাঁচের interview-তে DP-ই single সবচেয়ে বেশি tested *technique*। Climbing Stairs, House Robber, Coin Change, Unique Paths, LIS, Word Break আর Edit Distance — সবগুলোই খুব দেখা যায় এমন interview pattern — আর interviewer-রা শেষের table-এর চেয়ে বেশি শুনতে চান, তুমি state definition-টা মুখে বলছ কি না। [state-transition-thinking.md](state-transition-thinking.md)-এর 5-step doctrine-টা ঠিক সেই narration-এর script। Capstone mix-গুলো আছে [../13-interview-master-problems/](../13-interview-master-problems/README.md)-এ।

## Connection to competitive programming

CSES একটা গোটা chapter-ই DP-কে দিয়েছে, আর Codeforces-এ Div. 2 B থেকে উপরের দিকে problem-গুলো নিয়ম করে গল্পের আড়ালে একটা DP লুকিয়ে রাখে। Contest তারপর আরও ঠেলে দেয়: DP on trees, DP with bitmasks, segment tree (folder 11) বা convex hull দিয়ে optimize করা DP। এই folder-এর পরে USACO Guide-এর DP module ([usaco.guide/gold/intro-dp](https://usaco.guide/gold/intro-dp)) একটা চমৎকার next step।

## Recommended learning order (পড়ার ক্রম)

1. [README.md](README.md) — এই file-টা, map-এর জন্য।
2. [concept.md](concept.md) — DP কী, overlapping subproblems, memo vs tabulation।
3. [state-transition-thinking.md](state-transition-thinking.md) — core skill-টা: 5-step doctrine, সাতবার apply করা।
4. [visual-explanation.md](visual-explanation.md) — table-গুলো frame by frame ভরতে দেখো; step 3-এর পাশাপাশি পড়ো।
5. [patterns.md](patterns.md) — named family-গুলো আর তাদের trigger word।
6. [implementation.py](implementation.py) — চালাও, তারপর প্রতিটা function তার state definition থেকে নিজে re-derive করো।
7. [problems/README.md](problems/README.md) — tracker ধরে কাজ করো, easy থেকে hard।

## Source map

এই folder-এর সব source, link আর copying status আছে [source-map.md](source-map.md)-এ।