12 — Dynamic Programming¶
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/) — একটা 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/)। - Array আর 2D list (
../02-arrays-and-strings/)। - Memo table-এর জন্য hash map (
../05-hashing/)। - "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 গোনো | LeetCode 70 | 1D linear DP |
| Fibonacci Number — memoization-এর hello-world | LeetCode 509 | 1D linear DP |
| Min Cost Climbing Stairs — সবচেয়ে সস্তায় চূড়ায় ওঠো | LeetCode 746 | 1D linear DP |
| Dice Combinations — dice roll দিয়ে sum n বানানোর ways গোনো | CSES 1633 | 1D counting DP |
| Maximum Subarray — best contiguous sum (Kadane আসলে ছদ্মবেশী DP) | LeetCode 53 | 1D linear DP |
Medium¶
| Problem | Source | Pattern |
|---|---|---|
| House Robber — max লুট, পাশাপাশি দুটো বাড়ি নয় | LeetCode 198 | 1D take-or-skip |
| Coin Change — একটা amount বানাতে সবচেয়ে কম coin | LeetCode 322 | Unbounded knapsack (min) |
| Minimizing Coins — একই task, contest flavor | CSES 1634 | Unbounded knapsack (min) |
| Coin Combinations I — একটা sum বানানোর ordered ways গোনো | CSES 1635 | Unbounded counting |
| Unique Paths — m×n grid-এ lattice path গোনো | LeetCode 62 | Grid DP |
| Grid Paths — blocked cell-ওয়ালা grid-এ path গোনো | CSES 1638 | Grid DP with obstacles |
| Longest Increasing Subsequence | LeetCode 300 | LIS family |
| Partition Equal Subset Sum — array-টাকে দুটো সমান-sum ভাগে ভাঙা যায়? | LeetCode 416 | 0/1 knapsack (subset sum) |
| Word Break — string-টাকে কি dictionary-র শব্দে কাটা যায়? | LeetCode 139 | 1D DP over prefixes |
| Longest Common Subsequence | LeetCode 1143 | String DP |
| Book Shop — দাম আর page count-সহ classic 0/1 knapsack | CSES 1158 | 0/1 knapsack |
Hard¶
| Problem | Source | Pattern |
|---|---|---|
| Edit Distance — এক string থেকে আরেকটায় যেতে min insert/delete/replace | LeetCode 72 | String DP |
| Longest Increasing Subsequence in O(n log n) — LC 300 আবার করো, patience sorting দিয়ে | LeetCode 300 | LIS + binary search |
| Burst Balloons — balloon ফাটানোর order ঠিক করে coin maximize করো | LeetCode 312 | Interval DP |
Regular Expression Matching — . আর * matching implement করো |
LeetCode 10 | String DP, hard transitions |
| Codeforces থেকে চোখ বুজে বাছা যেকোনো 1400–1700 rated DP problem | Codeforces 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 আলাদা (
+vsmin/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-এর 5-step doctrine-টা ঠিক সেই narration-এর script। Capstone mix-গুলো আছে ../13-interview-master-problems/-এ।
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) একটা চমৎকার next step।
Recommended learning order (পড়ার ক্রম)¶
README.md— এই file-টা, map-এর জন্য।concept.md— DP কী, overlapping subproblems, memo vs tabulation।state-transition-thinking.md— core skill-টা: 5-step doctrine, সাতবার apply করা।visual-explanation.md— table-গুলো frame by frame ভরতে দেখো; step 3-এর পাশাপাশি পড়ো।patterns.md— named family-গুলো আর তাদের trigger word।implementation.py— চালাও, তারপর প্রতিটা function তার state definition থেকে নিজে re-derive করো।problems/README.md— tracker ধরে কাজ করো, easy থেকে hard।
Source map¶
এই folder-এর সব source, link আর copying status আছে source-map.md-এ।