# Problem Tracker — Dynamic Programming

[অধ্যায়ে ফিরুন](../README.md) · [সহজ ব্যাখ্যা ও ব্যবহার](../learning-guide.md) · [উৎসের তালিকা](../source-map.md)

> **লিংক পড়ার নিয়ম:** Source খুললে প্ল্যাটফর্মের মূল প্রশ্ন, Note file খুললে এই সাইটের ব্যাখ্যা ও সমাধান পাবেন। নোটগুলো আগে থেকেই লেখা আছে। `planned` হলো আপনার ব্যক্তিগত অনুশীলনের অবস্থা, নোট অনুপস্থিত থাকার চিহ্ন নয়। প্ল্যাটফর্মের কিছু প্রশ্নে লগইন বা Premium লাগতে পারে; স্থানীয় নোট সরাসরি পড়া যাবে।

এটা DP folder-এর working ledger। List-টা family-গুলোর ভেতর দিয়ে ওঠে ঠিক সেই order-এ, যেভাবে `patterns.md` শেখায়: 1D linear → grid → knapsack → LIS → string → teaser।

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

- এখানকার যেকোনো problem-এ code করার আগে, 5-step doctrine-টা কাগজে লেখো: state (শব্দে), transition, base cases, fill order, answer location।
- Cold অবস্থায় অন্তত 30 মিনিট চেষ্টা করো; আটকালে hint পড়ার আগে একটা ছোট্ট table হাতে ভরো — DP-র সেরা debugger হলো পেন্সিল।
- প্রতিটা problem-এর পরে এই folder-এ একটা note file লেখো — নাম হবে ঠিক **Note file** column-এ যা লেখা আছে, template: [../../templates/ds-problem-note-template.md](../../templates/ds-problem-note-template.md)। Note-এ তোমার state definition-এর বাক্যটা থাকতেই হবে।
- **Status** update করো: `planned` → `attempted` → `solved` → `revisit`।
- সব statement নিজেদের ভাষায় paraphrase করা; official statement-টা link-এ গিয়ে অবশ্যই পড়ো।

## How to read a row (একটা row কীভাবে পড়বে)

- **Pattern** হলো [../patterns.md](../patterns.md)-এর family — statement পড়ার আগে problem-এর title থেকেই আন্দাজ করো, আর তোমার hit rate track করো।
- **Inherits from** বলে নতুন problem-টা কোন আগের problem বা folder-এর উপর দাঁড়িয়ে; list-টা এমনভাবে সাজানো যে প্রতিটা row উপরের row-গুলোর muscle reuse করে।
- দুটো problem ইচ্ছে করে দুবার আছে (#15/#19 দুটোই LIS): দ্বিতীয়বারে algorithm বদলায়, problem নয় — ভালো tool দিয়ে আবার solve করাও নিজেই একটা skill।

## The per-problem ritual (প্রতি problem-এর রুটিন)

```text
1. read constraints first      (n tells you the target complexity)
2. name the suspected family   (from title + constraints alone)
3. write the 5 steps on paper  (state sentence is non-negotiable)
4. hand-fill a 4-element table (catches wrong transitions in 2 minutes)
5. code top-down memo first    (it mirrors the recursion you trust)
6. convert to bottom-up        (only if needed for speed/space/limits)
7. note file: state sentence, family guess vs reality, one mistake made
```

## The list

| # | Problem | Difficulty | Source | Pattern | Inherits from | Note file | Status |
| --- | --- | --- | --- | --- | --- | --- | --- |
| 1 | Fibonacci Number — আগে memoized, তারপর tabulated, তারপর O(1) space-এ implement করো | Easy | [LeetCode 509](https://leetcode.com/problems/fibonacci-number/) | 1D linear | Recursion (folder 06) | [001-fibonacci-three-ways.md](001-fibonacci-three-ways.md) | planned |
| 2 | Climbing Stairs — 1 আর 2 ধাপে n সিঁড়ি ওঠার ways গোনো | Easy | [LeetCode 70](https://leetcode.com/problems/climbing-stairs/) | 1D linear | #1, counting | [002-climbing-stairs.md](002-climbing-stairs.md) | planned |
| 3 | Min Cost Climbing Stairs — চূড়ায় ওঠার সবচেয়ে সস্তা route | Easy | [LeetCode 746](https://leetcode.com/problems/min-cost-climbing-stairs/) | 1D linear (min) | #2, +-কে min দিয়ে বদলাও | [003-min-cost-climbing-stairs.md](003-min-cost-climbing-stairs.md) | planned |
| 4 | Dice Combinations — dice roll করে মোট n বানানোর ways গোনো | Easy | [CSES 1633](https://cses.fi/problemset/task/1633) | 1D counting | #2, চওড়া look-back | [004-dice-combinations.md](004-dice-combinations.md) | planned |
| 5 | Maximum Subarray — best contiguous sum; Kadane-কে DP হিসেবে derive করো | Easy | [LeetCode 53](https://leetcode.com/problems/maximum-subarray/) | 1D linear, ends-at-i | Arrays (folder 02) | [005-maximum-subarray-as-dp.md](005-maximum-subarray-as-dp.md) | planned |
| 6 | House Robber — max লুট, পাশাপাশি বাড়ি নয় | Medium | [LeetCode 198](https://leetcode.com/problems/house-robber/) | 1D take-or-skip | #3 | [006-house-robber.md](006-house-robber.md) | planned |
| 7 | Unique Paths — right/down lattice path গোনো | Medium | [LeetCode 62](https://leetcode.com/problems/unique-paths/) | Grid DP | #2, 2D-তে | [007-unique-paths.md](007-unique-paths.md) | planned |
| 8 | Grid Paths — একই, কিন্তু কিছু cell blocked | Medium | [CSES 1638](https://cses.fi/problemset/task/1638) | Grid DP + obstacles | #7 | [008-grid-paths-with-traps.md](008-grid-paths-with-traps.md) | planned |
| 9 | Minimum Path Sum — cost-ওয়ালা grid-এর ভেতর দিয়ে সবচেয়ে সস্তা path | Medium | [LeetCode 64](https://leetcode.com/problems/minimum-path-sum/) | Grid DP (min) | #7, +-কে min দিয়ে বদলাও | [009-minimum-path-sum.md](009-minimum-path-sum.md) | planned |
| 10 | Coin Change — একটা amount-এর জন্য সবচেয়ে কম coin; [1,3,4], 6-এ greedy fail করে — নিজে verify করো | Medium | [LeetCode 322](https://leetcode.com/problems/coin-change/) | Unbounded knapsack (min) | #3, memo-র জন্য hashing | [010-coin-change-min.md](010-coin-change-min.md) | planned |
| 11 | Minimizing Coins — #10-এর contest version, বড় limit-সহ | Medium | [CSES 1634](https://cses.fi/problemset/task/1634) | Unbounded knapsack (min) | #10 | [011-minimizing-coins.md](011-minimizing-coins.md) | planned |
| 12 | Coin Combinations I — একটা sum বানানো ordered coin sequence গোনো | Medium | [CSES 1635](https://cses.fi/problemset/task/1635) | Unbounded counting | #4, #10 | [012-coin-combinations-i.md](012-coin-combinations-i.md) | planned |
| 13 | Partition Equal Subset Sum — array-টা কি দুটো সমান ভাগে ভাঙে? | Medium | [LeetCode 416](https://leetcode.com/problems/partition-equal-subset-sum/) | Subset-sum (0/1, boolean) | Knapsack skeleton | [013-partition-equal-subset-sum.md](013-partition-equal-subset-sum.md) | planned |
| 14 | Book Shop — budget-এর মধ্যে বই কিনে page maximize করো | Medium | [CSES 1158](https://cses.fi/problemset/task/1158) | 0/1 knapsack | #13, loop-direction-এর শিক্ষা | [014-book-shop-knapsack.md](014-book-shop-knapsack.md) | planned |
| 15 | Longest Increasing Subsequence — আগে O(n²); state anchor-টা লিখে রাখো | Medium | [LeetCode 300](https://leetcode.com/problems/longest-increasing-subsequence/) | LIS family | Ends-at-i anchoring | [015-lis-n-squared.md](015-lis-n-squared.md) | planned |
| 16 | Word Break — string-টাকে কি dictionary-র শব্দে কাটা যায়? | Medium | [LeetCode 139](https://leetcode.com/problems/word-break/) | 1D over string prefixes | Hashing (folder 05), #2 | [016-word-break.md](016-word-break.md) | planned |
| 17 | Longest Common Subsequence — longest shared (non-contiguous) sequence | Medium | [LeetCode 1143](https://leetcode.com/problems/longest-common-subsequence/) | String DP | Two-prefix state shape | [017-longest-common-subsequence.md](017-longest-common-subsequence.md) | planned |
| 18 | Edit Distance — এক string থেকে আরেকটায় min edit | Hard | [LeetCode 72](https://leetcode.com/problems/edit-distance/) | String DP | #17, three-way transition | [018-edit-distance.md](018-edit-distance.md) | planned |
| 19 | LIS in O(n log n) — patience/binary-search trick দিয়ে #15 আবার করো | Hard | [LeetCode 300](https://leetcode.com/problems/longest-increasing-subsequence/) | LIS + binary search | #15, binary search (math level 07) | [019-lis-n-log-n.md](019-lis-n-log-n.md) | planned |
| 20 | House Robber on a circle — প্রথম আর শেষ বাড়ি adjacent (#6 দুবার চালাও) | Hard | [LeetCode 213 · House Robber II](https://leetcode.com/problems/house-robber-ii/) | 1D + case split | #6 | [020-house-robber-circular.md](020-house-robber-circular.md) | planned |
| 21 | Burst Balloons — coin maximize করা pop order; "last popped"-টা ভাবো | Hard | [LeetCode 312](https://leetcode.com/problems/burst-balloons/) | Interval DP | patterns.md-র interval teaser | [021-burst-balloons.md](021-burst-balloons.md) | planned |
| 22 | Regular Expression Matching — `.` আর `*` support করো | Hard | [LeetCode 10](https://leetcode.com/problems/regular-expression-matching/) | String DP, hard transitions | #17, #18 | [022-regex-matching.md](022-regex-matching.md) | planned |
| 23 | DAG-এ longest path — dependency graph-এর উপর গোনো বা maximize করো | Hard | self-exercise (build on ../09-graphs/topological-sort.md) | DP on DAG | Graphs (folder 09) topological order | [023-longest-path-dag.md](023-longest-path-dag.md) | planned |
| 24 | Codeforces থেকে চোখ-বুজে একটা 1400–1700 DP pick — code করার আগে family-র নাম বলো | Hard | [Codeforces 455A · Boredom](https://codeforces.com/problemset/problem/455/A) · [অন্য প্রশ্ন](https://codeforces.com/problemset/) | Pattern recognition | পুরো folder | [024-codeforces-blind-pick.md](024-codeforces-blind-pick.md) | planned |

## Milestones

- #6-এর পরে: 1D problem-এর জন্য 5-step doctrine muscle memory।
- #12-এর পরে: "count the ways" আর "find the best" সাথে সাথে আলাদা করতে পারবে, আর জানবে কোনটার কোন base case লাগে।
- #14-এর পরে: knapsack-এর loop-direction নিয়মটা (right-to-left = 0/1, left-to-right = unbounded) মাথায় গেঁথে যাবে।
- #18-এর পরে: two-string DP table আর ভয় দেখাবে না।
- #24-এর পরে: অদেখা DP problem-এর family-র নাম শুধু trigger word থেকেই বলতে পারবে।

## When you get stuck (আটকে গেলে)

| Symptom | Where to go |
| --- | --- |
| State-ই খুঁজে পাচ্ছ না | জিজ্ঞেস করো "LAST decision-টার কী জানা লাগে?" — [../state-transition-thinking.md](../state-transition-thinking.md), LIS-এর শিক্ষাটা |
| State পাওয়া গেছে, transition আসছে না | State-এ information missing; একটা anchor বা একটা dimension যোগ করো (একই file, mistakes table) |
| Table ভরে কিন্তু উত্তর ভুল | [../visual-explanation.md](../visual-explanation.md)-এর frame-এর সাথে মিলিয়ে n = 4 হাতে ভরো; যেখানে divergence, সেখানেই bug |
| Counting-এর উত্তর একটা factor-এ ভুল | Base-case identity check: counting শুরু 1 দিয়ে, minimizing শুরু 0 দিয়ে — বাকিটা infinity |
| 0/1 knapsack একটা item দুবার নিচ্ছে | Loop direction — [../implementation.py](../implementation.py)-এর knapsack docstring-এর warning দেখো |
| Memoized version recursion limit-এ ঠেকছে | Tabulation-এ convert করো; fill order-টা তোমার recursion order-এর উল্টো |

এখানে কোনো problem `solved` mark করা মানে: judge pass করেছে এবং তোমার note file-এ এমন একটা state definition-এর বাক্য আছে, যেটা interview-তে মুখে দাঁড় করিয়ে defend করতে পারবে।