State-Transition Thinking — The 5-Step Doctrine¶

পৃথিবীর প্রতিটা DP problem একই পাঁচটা প্রশ্ন দিয়ে solve হয়, একই order-এ করা। এই file সেই প্রশ্নগুলো সাতবার করেছে, সাতটা classic problem-এর উপর, যতক্ষণ না ছন্দটা automatic হয়ে যায়।

The doctrine¶

একটা লাইনও code লেখার আগে এগুলোর উত্তর দাও — শব্দে, কাগজে:

STATE — dp[...] মানে কী, এক বাক্যে? ("dp[i] = ... করার ways-এর সংখ্যা")
TRANSITION — ছোট state থেকে একটা state কীভাবে তৈরি হয়? (Equation-টা, plus কেন।)
BASE CASES — কোন state-গুলো এমনিই জানা?
FILL ORDER — কোন order-এ state-গুলো compute করলে যা-ই পড়া হয় তা আগেই লেখা থাকে?
ANSWER — Final উত্তরটা কোন cell-এ থাকে?

Step 1-ই কাজের 80%। State definition সঠিক হলে transition প্রায় নিজে নিজেই লেখা হয়ে যায়; ঝাপসা হলে problem-টা unsolvable হয়ে দাঁড়ায়। Discipline-টা: "dp[i] মানে ___" বাক্যটা না থেমে শেষ করতে পারার আগে কখনো dp[i] = ... লিখো না।

State খুঁজে পাওয়ার নির্ভরযোগ্য উপায়টা: কল্পনা করো একটা optimal/complete solution-এর শেষ decision-টা নিচ্ছ, আর জিজ্ঞেস করো — "এই decision-এর আগের সবকিছু সম্পর্কে আমার কী কী জানা লাগত?" ওই অল্প কয়টা সংখ্যাই তোমার state।

Problem 1 — Climbing Stairs¶

Task, নিজেদের ভাষায়: তুমি n-টা সিঁড়ি ওঠো, একবারে 1 বা 2 ধাপ করে। চূড়ায় পৌঁছানোর distinct উপায় গোনো। (LeetCode 70)

State। dp[i] = step i-তে দাঁড়ানোর distinct ways-এর সংখ্যা।
Transition। Step i-তে ঢোকার শেষ move-টা হয় i-1 থেকে একটা 1-step, নয় i-2 থেকে একটা 2-step। এই দুটো দল disjoint আর সবকিছু cover করে, তাই

dp[i] = dp[i-1] + dp[i-2]

Base cases। dp[0] = 1 (শুরুতে থাকার একটাই উপায়: কিছুই না করা), dp[1] = 1।
Fill order। i = 2, 3, ..., n — প্রতিটা cell কেবল আগের cell পড়ে।
Answer। dp[n]।

খেয়াল করো: এটা ছদ্মবেশ-পরা Fibonacci। অনেক counting problem-ই তাই।

Problem 2 — House Robber¶

Task, নিজেদের ভাষায়: এক সারিতে বাড়ি, প্রত্যেকটায় কিছু টাকা; পাশাপাশি দুটো বাড়ি লুট করা যাবে না; লুট maximize করো। (LeetCode 198)

State। dp[i] = প্রথম i+1-টা বাড়ি (বাড়ি 0..i) থেকে পাওয়া সম্ভব maximum লুট, বাড়ি i নিজে লুট হয়েছে কি না — তার কোনো শর্ত ছাড়াই।
Transition। শেষ decision: বাড়ি i লুট করো, না skip করো।

dp[i] = max( dp[i-1],              # skip house i
             dp[i-2] + money[i] )  # rob it -> i-1 is forbidden

এটা কেন কাজ করে: i লুট করলে, তার আগে best যা করা যেত তা হলো বাড়ি 0..i-2-এর উপর best-টা; "no adjacent" নিয়মটা enforce হয় কোন ছোট state-এর দিকে হাত বাড়াচ্ছি, তা দিয়ে। 3. Base cases। dp[0] = money[0], dp[1] = max(money[0], money[1])। 4. Fill order। i = 2, ..., n-1। 5. Answer। dp[n-1]।

State-design-এর শিক্ষা: beginner-এর instinct হয় দুটো array ("i লুট করলে best" / "না করলে best")। সেটাও চলে — কিন্তু choice-টাকে state-এর বদলে transition-এ fold করলে একটা array-তেই হয়ে যায়। দুটোই বৈধ; doctrine শুধু দাবি করে — সচেতনভাবে বাছো।

Problem 3 — Coin Change (minimum coins)¶

Task, নিজেদের ভাষায়: coin denomination-গুলো দেওয়া (প্রত্যেকটার unlimited supply) আর একটা amount; সবচেয়ে কম কয়টা coin দিয়ে amount-টা বানানো যায় বের করো, না গেলে impossible বলো। (LeetCode 322)

State। dp[a] = ঠিক amount a বানাতে দরকারি minimum coin-সংখ্যা।
Transition। শেষ decision: শেষে কোন coin c বসানো হয়েছিল? তার আগে আমাদের ছিল amount a - c।

dp[a] = 1 + min( dp[a - c]  for every coin c with c <= a )

Base cases। dp[0] = 0 (শূন্য বানাতে শূন্য coin)। বাকি সব infinity দিয়ে initialize করো, মানে "এখনো বানানো যায় বলে জানা নেই"।
Fill order। a = 1, 2, ..., amount।
Answer। dp[amount], আর এখনো infinity থাকলে -1।

এখানে greedy কেন fail করে (আর DP করে না): coins [1, 3, 4], amount 6। Greedy আগে 4 ধরে, তারপর 1, তারপর 1 → 3 coins। DP খুঁজে পায় 3 + 3 → 2 coins। DP জেতে কারণ সব শেষ coin-এর উপর min প্রতিটা history বিবেচনা করে; greedy একটাতেই commit করে ফেলে।

Problem 4 — Grid Paths¶

Task, নিজেদের ভাষায়: একটা m × n grid-এর top-left থেকে bottom-right-এ path গোনো, শুধু right বা down চলে। (LeetCode 62 — Unique Paths; obstacle version: CSES 1638)

State। dp[r][c] = start cell থেকে cell (r, c) পর্যন্ত path-এর সংখ্যা।
Transition। (r, c)-তে ঢোকার শেষ move-টা এসেছে উপর থেকে বা বাঁ থেকে:

dp[r][c] = dp[r-1][c] + dp[r][c-1]

(Obstacle থাকলে: cell-টা blocked হলে dp[r][c] = 0, যা-ই হোক।) 3. Base cases। dp[0][0] = 1। Row 0 / column 0-র cell-গুলোর ঢোকার direction একটাই (grid-এর বাইরের neighbor-দের 0 ধরলে এটা এমনিই handle হয়)। 4. Fill order। Row by row, বাঁ থেকে ডানে — প্রতিটা cell-এর dependency (up, left) আগেই filled। 5. Answer। dp[m-1][n-1]।

Step 4-এর সবচেয়ে পরিষ্কার illustration এটাই: transition arrow-গুলোর geometry-ই fill order ঠিক করে দেয়।

Problem 5 — Longest Increasing Subsequence (LIS)¶

Task, নিজেদের ভাষায়: একটা array-র longest strictly increasing subsequence-এর (contiguous হতে হবে না) length বের করো। (LeetCode 300)

State। dp[i] = ঠিক index i-তে শেষ হওয়া longest increasing subsequence-এর length।
Transition। শেষ decision: subsequence-এ a[i]-এর ঠিক আগে কোন element ছিল? ছোট value-ওয়ালা যেকোনো আগের j:

dp[i] = 1 + max( dp[j]  for j < i  if a[j] < a[i] ),   or 1 if no such j

Base cases। প্রতিটা dp[i] শুরু হয় 1 দিয়ে (element-টা একা)।
Fill order। i = 0, 1, ..., n-1।
Answer। max(dp) — dp[n-1] নয়, কারণ best subsequence যেকোনো জায়গায় শেষ হতে পারে।

State-design-এর শিক্ষা — এই file-এর সবচেয়ে শিক্ষণীয়টা: dp[i]-কে "প্রথম i element-এর LIS" define করলে (ends-at anchor ছাড়া) এমন একটা state পাও যার কোনো usable transition নেই — একটা prefix-এর best length জানা তোমাকে কিছুই বলে না a[i] সেটাকে extend করতে পারে কি না। "ঠিক i-তে শেষ হয়" যোগ করলেই transition-এর দরকারি একটামাত্র fact-টা পিন হয়ে যায়: শেষ value-টা। Transition আসতে না চাইলে বুঝবে state-এ information missing। Anchor করো।

(Patience sorting + binary search দিয়ে একটা O(n log n) version আছে — এটা পাকা হওয়ার পরে problem tracker-এ তার সাথে দেখা হবে।)

Problem 6 — 0/1 Knapsack¶

Task, নিজেদের ভাষায়: n-টা item, প্রত্যেকটার একটা weight আর একটা value; knapsack-এ সর্বোচ্চ capacity W ধরে; প্রতিটা item সর্বোচ্চ একবার; total value maximize করো। (Classic; contest version: CSES 1158 — Book Shop।)

State। dp[i][w] = শুধু প্রথম i-টা item ব্যবহার করে, total weight সর্বোচ্চ w রেখে best value। দুটো dimension কারণ শেষ decision-এর দুটো fact লাগে: কোন item-গুলো এখনো টেবিলে আছে, আর কতটা জায়গা বাকি।
Transition। শেষ decision: item i নাও, না রেখে দাও।

dp[i][w] = max( dp[i-1][w],                              # leave item i
                dp[i-1][w - wt[i]] + val[i]  if wt[i] <= w )  # take it

Crucial detail: item i নিলে হাত যায় row i-1-এ — যে row-তে item i তখনো available ছিল না — আর ঠিক এটাই "at most once" enforce করে। 3. Base cases। সব w-এর জন্য dp[0][w] = 0 (item নেই, value নেই)। 4. Fill order। Item by item (rows), একটা row-র ভেতরে যেকোনো order। 5. Answer। dp[n][W]।

Bonus pattern: row i যেহেতু শুধু row i-1 পড়ে, table-টা একটা array-তে compress হয় — কিন্তু তখন w-কে ডান থেকে বাঁয়ে ভরতে হবে, যাতে প্রতিটা item একবারই গোনা হয়। এক array নিয়ে বাঁ থেকে ডানে ভরলে সেটা নিঃশব্দে unbounded knapsack হয়ে যায়। ওই একটা মাত্র loop direction-ই দুটো problem-এর পুরো পার্থক্য।

Problem 7 — Edit Distance (sketch level)¶

Task, নিজেদের ভাষায়: string a-কে string b বানাতে minimum কয়টা single-character insert, delete বা replacement লাগে। (LeetCode 72)

State। dp[i][j] = a-র প্রথম i-টা character-কে b-র প্রথম j-টা character বানানোর minimum operations।
Transition। শেষ character দুটো a[i-1] আর b[j-1]-এর দিকে তাকাও:

if a[i-1] == b[j-1]:  dp[i][j] = dp[i-1][j-1]            # free match
else:                 dp[i][j] = 1 + min( dp[i-1][j],    # delete from a
                                          dp[i][j-1],    # insert into a
                                          dp[i-1][j-1] ) # replace

Base cases। dp[i][0] = i (সব delete করো), dp[0][j] = j (সব insert করো)।
Fill order। Row by row, বাঁ থেকে ডানে।
Answer। dp[len(a)][len(b)]।

a = "cat", b = "cut"-এর ছোট্ট table:

        ""  c   u   t
    ""   0  1   2   3
    c    1  0   1   2
    a    2  1   1   2
    t    3  2   2   1     -> answer 1 (replace 'a' with 'u')

এই grid-আকৃতি — দুটো string prefix-এর উপর dp[i][j] — একটা গোটা family-র skeleton (LCS, alignment, regex matching)। দেখো patterns.md।

Common state-design mistakes (সাধারণ ভুল)¶

Mistake	Symptom	Fix
State-টা শব্দে বলার আগেই code করা	Transition-গুলো খামখেয়ালি লাগে; bug খুঁজে পাওয়া যায় না	আগে "`dp[i]` মানে ___" বাক্যটা শেষ করো, সবসময়
State-এ information missing	কোনো valid transition exist করে না (LIS-এর শিক্ষাটা)	জিজ্ঞেস করো শেষ decision-এর কী জানা লাগে; সেটা state-এ যোগ করো
State বেশি বহন করছে (যেমন পুরো chosen set)	State-এর সংখ্যা exponentially ফেটে যায়	শুধু যা future decision-এর কাজে লাগে তা রাখো; history ফেলে দাও
"ends at i" vs "first i elements" গুলিয়ে ফেলা	উত্তর ভুল cell-এ, বা transition impossible	Anchor-টা explicitly ঠিক করো; step 5 আবার check করো
Base-এ ভুল identity	Count একটা factor-এ ভুল, min infinity-তে আটকে	Counting শুরু হয় `dp[0] = 1` দিয়ে; minimizing শুরু হয় `dp[0] = 0` দিয়ে, বাকিটা infinity
Dependency ভাঙা fill order	Zero/garbage পড়ে, উত্তর ছোট আসে	Transition arrow-গুলো আঁকো; এমনভাবে ভরো যাতে arrow সবসময় finished cell-এর দিকে তাক করে
1D knapsack ভুল direction-এ ভরা	0/1 নিঃশব্দে unbounded হয়ে যায়	0/1-এর জন্য ডান-থেকে-বাঁ, unbounded-এর জন্য বাঁ-থেকে-ডান
উত্তর `max(dp)` হলেও `dp[n-1]` report করা	Table সঠিক, final উত্তর ভুল	Step 5 একটা সত্যিকারের step — উত্তর কোথায় থাকে, মুখে বলো

The drill¶

প্রতিটা নতুন DP problem-এর জন্য, editor খোলার আগে পাঁচটা উত্তর কাগজে লেখো। Interview-তে মুখে বলো — state definition-এর বাক্যটাই ঠিক সেই জিনিস, যেটা একজন strong candidate-এর মতো শোনায়। তারপর তোমার table-গুলো মিলিয়ে নাও visual-explanation.md-এর সাথে আর code মিলিয়ে নাও implementation.py-এর সাথে।