Skip to content

DP Patterns — The Named Families

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)
  • House Robber (LeetCode 198)
  • Maximum Subarray (LeetCode 53) — Kadane আসলে dp[i] = max(a[i], dp[i-1] + a[i])
  • Dice Combinations (CSES 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)
  • Grid Paths with traps (CSES 1638)
  • Minimum Path Sum (LeetCode 64)

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)

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), Minimizing Coins (CSES 1634) — count minimize করো
  • Coin Combinations I (CSES 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)

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)
  • 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)
  • Edit Distance (LeetCode 72)
  • Word Break (LeetCode 139) — একটা 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) — 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।
  • Representative tasks: DAG-এ longest path, DAG-এ path গোনা — graph + DP combo-টা দেখো ../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-এর পুরো 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) contest DP-কে প্রায় একই family-রেখায় সাজিয়েছে।