# State-Transition Thinking — The 5-Step Doctrine

[অধ্যায়ের সূচি](README.md) · [সহজ ব্যাখ্যা ও বাস্তব ব্যবহার](learning-guide.md) · [অনুশীলন ও সমাধান](problems/README.md)

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

---

## The doctrine

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

1. **STATE** — `dp[...]` *মানে* কী, এক বাক্যে? ("`dp[i]` = ... করার ways-এর সংখ্যা")
2. **TRANSITION** — ছোট state থেকে একটা state কীভাবে তৈরি হয়? (Equation-টা, plus *কেন*।)
3. **BASE CASES** — কোন state-গুলো এমনিই জানা?
4. **FILL ORDER** — কোন order-এ state-গুলো compute করলে যা-ই পড়া হয় তা আগেই লেখা থাকে?
5. **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](https://leetcode.com/problems/climbing-stairs/))

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

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

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

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

---

## Problem 2 — House Robber

Task, নিজেদের ভাষায়: এক সারিতে বাড়ি, প্রত্যেকটায় কিছু টাকা; পাশাপাশি দুটো বাড়ি লুট করা যাবে না; লুট maximize করো। ([LeetCode 198](https://leetcode.com/problems/house-robber/))

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

   ```text
   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](https://leetcode.com/problems/coin-change/))

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

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

3. **Base cases।** `dp[0] = 0` (শূন্য বানাতে শূন্য coin)। বাকি সব infinity দিয়ে initialize করো, মানে "এখনো বানানো যায় বলে জানা নেই"।
4. **Fill order।** `a = 1, 2, ..., amount`।
5. **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](https://leetcode.com/problems/unique-paths/); obstacle version: [CSES 1638](https://cses.fi/problemset/task/1638))

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

   ```text
   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](https://leetcode.com/problems/longest-increasing-subsequence/))

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

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

3. **Base cases।** প্রতিটা `dp[i]` শুরু হয় 1 দিয়ে (element-টা একা)।
4. **Fill order।** `i = 0, 1, ..., n-1`।
5. **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](https://cses.fi/problemset/task/1158)।)

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

   ```text
   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](https://leetcode.com/problems/edit-distance/))

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

   ```text
   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
   ```

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

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

```text
        ""  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](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](visual-explanation.md)-এর সাথে আর code মিলিয়ে নাও [implementation.py](implementation.py)-এর সাথে।