Skip to content

Problem Tracker — Dynamic Programming

এটা 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। Note-এ তোমার state definition-এর বাক্যটা থাকতেই হবে।
  • Status update করো: planned → attempted → solved → revisit।
  • সব statement নিজেদের ভাষায় paraphrase করা; official statement-টা link-এ গিয়ে অবশ্যই পড়ো।

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

  • Pattern হলো ../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-এর রুটিন)

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

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