အခန်း ၂၃ - 2-D Dynamic Programming

အခန်း ၂၂ မှာ — dp[i] ဆိုတဲ့ ၁ တန်း (1-D) state နဲ့ ပြဿနာတွေ ဖြေခဲ့ပါတယ် ("index i ထိ အကောင်းဆုံး")။ ဒါပေမယ့် ပြဿနာ အများကြီးမှာ — အဖြေ တစ်ခုကို သတ်မှတ်ဖို့ အညွှန်း ၂ ခု လိုတယ် —

Grid ပေါ်မှာ လမ်းကြောင်း ရှာတာ — "row i, column j ထိ" (အညွှန်း ၂ ခု)။
String ၂ ခု နှိုင်းတာ — "string A ရဲ့ ပထမ i လုံး၊ string B ရဲ့ ပထမ j လုံး" (အညွှန်း ၂ ခု)။

ဒီလို ပြဿနာတွေကို 2-D DP နဲ့ ဖြေတယ် — state က dp[i][j] ဆိုတဲ့ ဇယား (table) ဖြစ်လာတယ်။ 2-D DP က 1-D ထက် ခက်တယ် ထင်ရပေမယ့် — တကယ်တော့ table ကို ပုံဆွဲပြီး စဉ်းစားရင် အလွန် မြင်သာတယ်။ ဒီအခန်းမှာ — table ဖွဲ့စည်းပုံ၊ transition ဦးတည်ချက် (အပေါ်/ဘယ်/ထောင့်ဖြတ်)၊ ပြီးတော့ Grid DP, String DP, Knapsack ဆိုတဲ့ classic ပြဿနာ ၅ ခု ဖြေသွားပါမယ်။

2-D State နဲ့ DP Table

2-D DP ရဲ့ state က dp[i][j] — အညွှန်း ၂ ခုနဲ့ သတ်မှတ်တဲ့ table တစ်ခုပါ။ i က row (အတန်း)၊ j က column (ကော်လံ)။ dp[i][j] ဆိုတာ "row i, column j အခြေအနေထိ ရောက်တဲ့ အကောင်းဆုံး အဖြေ" ကို ကိုယ်စားပြုတယ်။

1-D DP မှာ "index i ထိ" တွက်သလို — 2-D DP မှာ cell တစ်ခုစီကို — အရင် cell တွေ (အိမ်နီးချင်း) ကနေ တွက်ပြီး table ကို ဖြည့်တက်တာပါ။

Transition ဦးတည်ချက် — အပေါ်/ဘယ်/ထောင့်ဖြတ်

2-D DP ရဲ့ အနှစ်သာရက — dp[i][j] ကို ဘယ် cell တွေကနေ တွက်လဲ ဆိုတာပါ။ အများဆုံး အသုံးပြုတဲ့ ၃ ဦးတည်ချက် —

        dp[i-1][j-1]   dp[i-1][j]
          (ထောင့်ဖြတ်)   (အပေါ်)
              ↘            ↓
        dp[i][j-1]  →  dp[i][j]
          (ဘယ်)

အပေါ် (dp[i-1][j]) — အပေါ်တန်းကနေ ဆင်းလာတာ။
ဘယ် (dp[i][j-1]) — ဘယ်ဘက်ကနေ လာတာ။
ထောင့်ဖြတ် (dp[i-1][j-1]) — ဖြတ်လာတာ။

ပြဿနာ အလိုက် — ဒီ ၃ ခုထဲက ဘယ်ဟာ သုံးမလဲ ကွဲတယ်။ Grid path က အပေါ် + ဘယ်၊ string နှိုင်းတာတွေက ထောင့်ဖြတ် ပါ များတယ်။ ဒါက 2-D DP ပြဿနာ ဖြေတဲ့အခါ အရင်ဆုံး ရှာရမယ့် အချက်ပါ။

Grid DP vs String DP

2-D DP ပြဿနာ အများစုက အမျိုးအစား ၂ မျိုး —

Grid DP — dp[i][j] က grid cell (i,j) ကို တိုက်ရိုက် ကိုယ်စားပြု (Unique Paths, Min Path Sum)။ table size = grid size။
String DP — dp[i][j] က "string A ရဲ့ ပထမ i လုံး နဲ့ string B ရဲ့ ပထမ j လုံး" ကို ကိုယ်စားပြု (LCS, Edit Distance)။ i=0 / j=0 က "string ဗလာ" ကို ကိုယ်စားပြုလို့ — table size = (m+1) × (n+1)။

မှတ်ရန်: String DP မှာ row/column ကို 0 ကစ ရေတွက်တဲ့အခါ — dp[i][j] ရဲ့ i က "string A ရဲ့ ပထမ i လုံး" (index မဟုတ်) ကို ဆိုလိုတယ်။ ဒါကြောင့် character ကို ယှဉ်တဲ့အခါ A[i-1] နဲ့ B[j-1] (၁ နုတ်) ကို သုံးရတယ်။ ဒီ "off-by-one" က string DP ရဲ့ အမှား အဖြစ်ဆုံး အချက်ပါ။

Space Optimization — Overview

2-D DP table က space $O(m \times n)$ ယူတယ်။ ဒါပေမယ့် dp[i][j] ကို တွက်ဖို့ အပေါ်တန်း (i-1) နဲ့ လက်ရှိတန်း (i) ၂ တန်းပဲ လိုလေ့ ရှိတယ်။ ဒါဆို — table တစ်ခုလုံး မသိမ်းဘဲ — တန်း ၂ ခု (ဒါမှမဟုတ် ၁ တန်း ကို သတိနဲ့ overwrite) ပဲ သိမ်းရင် — space ကို $O(n)$ အထိ လျှော့လို့ ရတယ်။

ဒါက "rolling array" technique ပါ။ Logic ပိုရှုပ်လို့ — ဒီအခန်းမှာ ပြဿနာ အများစုကို full 2-D table နဲ့ ပြ (နားလည် လွယ်အောင်)၊ ပြီးမှ optimization ကို မှတ်ချက် အဖြစ် ထည့်ပါမယ်။

Real-world Examples

Text Comparison / Diff Tool — git diff, editor ရဲ့ "ဘယ်စာကြောင်း ပြောင်းသွားလဲ" — string ၂ ခုကြား Longest Common Subsequence / Edit Distance ပေါ်မှာ အခြေခံတယ်။
Spell Check / Autocorrect — "ရိုက်မိတဲ့ စာလုံး နဲ့ အနီးစပ်ဆုံး မှန်တဲ့ စာလုံး" — Edit Distance (ဘယ်နှ လုံး ပြင်ရမလဲ) နဲ့ တိုင်းတာ။
Route Cost in Grid — warehouse / map grid ပေါ်မှာ "အကုန်ကျ အနည်းဆုံး လမ်း" — Min Path Sum။
Budget / Resource Allocation — budget အကန့်အသတ်နဲ့ "value အများဆုံး ရအောင် ဘယ် item ရွေးမလဲ" — 0/1 Knapsack။
DNA / Sequence Alignment — bioinformatics မှာ DNA sequence ၂ ခု နှိုင်းတာ — LCS / Edit Distance ရဲ့ ကြီးထွားပုံ။

Questions

2-D DP ပြဿနာ ဖြေတဲ့အခါ — table ကို ပုံဆွဲပြီး၊ (၁) dp[i][j] ဘာလဲ (state)၊ (၂) ဘယ် cell ကနေ တွက်လဲ (transition)၊ (၃) ပထမ row/column (base case) — ဆိုတာ ရှာတာပါ။ classic ၅ ခု ဖြေကြည့်ရအောင်။

၁။ Unique Paths

m × n grid မှာ — ဘယ်အပေါ်ထောင့် (0,0) ကစ — ညာ ဒါမှမဟုတ် အောက် ပဲ ရွေ့နိုင်ပြီး — ညာအောက်ထောင့် (m-1,n-1) ထိ ရောက်ဖို့ ကွဲပြားတဲ့ လမ်း ဘယ်နှ မျိုး ရှိလဲ။

Input: m = 3, n = 3
Output: 6

ရှင်းလင်းချက်

State: dp[i][j] = (0,0) ကနေ cell (i,j) ထိ ရောက်တဲ့ လမ်း အရေအတွက်။
Transition: cell (i,j) ကို — အပေါ် (i-1,j) ကနေ (အောက်ဆင်း) ဒါမှမဟုတ် ဘယ် (i,j-1) ကနေ (ညာသွား) ရောက်နိုင်လို့ → dp[i][j] = dp[i-1][j] + dp[i][j-1]။
Base case: ပထမ row နဲ့ ပထမ column အကုန် 1 (လမ်းကြောင်း တစ်ခုတည်း — တန်းသွား ဒါမှမဟုတ် တန်းဆင်း)။

m = 3, n = 3 table ဖြည့်ကြည့်ရအောင် —

        j=0  j=1  j=2
   i=0 [ 1 ][ 1 ][ 1 ]      ← ပထမ row အကုန် 1
   i=1 [ 1 ][ 2 ][ 3 ]      dp[1][1] = 1+1 = 2,  dp[1][2] = 1+2 = 3
   i=2 [ 1 ][ 3 ][ 6 ]      dp[2][2] = dp[1][2] + dp[2][1] = 3+3 = 6 ✓

Time Complexity: $O(m \times n)$ - cell တစ်ခုစီ တစ်ခါ။
Space Complexity: $O(m \times n)$ - table (rolling array နဲ့ $O(n)$ လျှော့နိုင်)။

Java Solution

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) dp[i][0] = 1;      // ပထမ column
        for (int j = 0; j < n; j++) dp[0][j] = 1;      // ပထမ row
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // အပေါ် + ဘယ်
            }
        }
        return dp[m - 1][n - 1];
    }
}

၂။ Minimum Path Sum

m × n grid မှာ cell တစ်ခုစီ တန်ဖိုး (cost) ရှိ။ ဘယ်အပေါ်ထောင့်ကစ — ညာ/အောက် ပဲ ရွေ့ပြီး — ညာအောက်ထောင့်ထိ — ဖြတ်သွားတဲ့ cell တွေရဲ့ ပေါင်းလဒ် အနည်းဆုံး ပြန်ပါ။

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
   (လမ်း 1→3→1→1→1 = 7)

ရှင်းလင်းချက်

Unique Paths နဲ့ တူ — ကွာတာက "လမ်း ရေတွက်" မဟုတ်ဘဲ "cost အနည်းဆုံး" ။

State: dp[i][j] = (0,0) ကနေ (i,j) ထိ — ပေါင်းလဒ် အနည်းဆုံး။
Transition: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]) — အပေါ်နဲ့ ဘယ် ၂ ခုထဲက အသက်သာတာ ရွေး။
Base case: dp[0][0] = grid[0][0]၊ ပထမ row/column က — တစ်ဘက်တည်းကပဲ လာနိုင်လို့ ဆက်ပေါင်း။

grid = [[1,3,1],[1,5,1],[4,2,1]] table —

   grid:              dp (ပေါင်းလဒ် အနည်းဆုံး):
   1 3 1              1 4 5
   1 5 1     →        2 7 6
   4 2 1              6 8 7
   dp[2][2] = 1 + min(dp[1][2]=6, dp[2][1]=8) = 1+6 = 7 ✓

Time Complexity: $O(m \times n)$ ။
Space Complexity: $O(m \times n)$ - table (in-place ဆို $O(1)$ )။

Java Solution

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for (int j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];  // ပထမ row
        for (int i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];  // ပထမ column
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m - 1][n - 1];
    }
}

၃။ Longest Common Subsequence (LCS)

string ၂ ခု text1, text2 ပေးထားသည်။ ၂ ခုစလုံးမှာ ပါတဲ့ — အရှည်ဆုံး common subsequence (အစဉ်အတိုင်း၊ ဆက်တိုက် မဖြစ်လည်း ရ) ရဲ့ အရှည် ပြန်ပါ။

Input: text1 = "abcde", text2 = "ace"
Output: 3
   (common subsequence "ace" — အရှည် 3)

ရှင်းလင်းချက်

ဒါက String DP ပါ — table size (m+1) × (n+1) (row/column 0 = string ဗလာ)။

State: dp[i][j] = text1 ရဲ့ ပထမ i လုံး နဲ့ text2 ရဲ့ ပထမ j လုံးကြား LCS အရှည်။
Transition:
- စာလုံး တူ (text1[i-1] == text2[j-1]) → ထောင့်ဖြတ် + 1 → dp[i][j] = dp[i-1][j-1] + 1။
- မတူ → အပေါ်နဲ့ ဘယ် ၂ ခုထဲက max → dp[i][j] = max(dp[i-1][j], dp[i][j-1])။
Base case: dp[0][*] = 0၊ dp[*][0] = 0 (string ဗလာနဲ့ LCS = 0)။

text1 = "abcde", text2 = "ace" table —
LCS DP Table — abcde / ace

Time Complexity: $O(m \times n)$ ။
Space Complexity: $O(m \times n)$ - table။

Java Solution

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];        // row/col 0 = ဗလာ (base = 0)
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;           // တူ → ထောင့်ဖြတ်+1
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);  // မတူ → max
                }
            }
        }
        return dp[m][n];
    }
}

၄။ Edit Distance

string word1 ကို word2 ဖြစ်အောင် ပြောင်းဖို့ — operation အနည်းဆုံး ပြန်ပါ။ operation ၃ မျိုး — insert (ထည့်)၊ delete (ဖျက်)၊ replace (အစားထိုး)။

Input: word1 = "horse", word2 = "ros"
Output: 3
   (horse → rorse (replace h→r) → rose (delete r) → ros (delete e))

ရှင်းလင်းချက်

String DP — "spell check / diff tool" ရဲ့ အနှစ်သာရ။

State: dp[i][j] = word1 ပထမ i လုံးကို word2 ပထမ j လုံး ဖြစ်အောင် — operation အနည်းဆုံး။
Transition:
- စာလုံး တူ → ဘာမှ မလို → dp[i][j] = dp[i-1][j-1] (ထောင့်ဖြတ်)။
- မတူ → operation ၃ မျိုးထဲက min + 1:
  - replace → dp[i-1][j-1] (ထောင့်ဖြတ်)
  - delete → dp[i-1][j] (အပေါ်)
  - insert → dp[i][j-1] (ဘယ်)
Base case: dp[i][0] = i (လုံး i ခု ဖျက်)၊ dp[0][j] = j (လုံး j ခု ထည့်)။

word1 = "horse", word2 = "ros" table —
Edit Distance DP Table — horse / ros

Time Complexity: $O(m \times n)$ ။
Space Complexity: $O(m \times n)$ - table။

Java Solution

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) dp[i][0] = i;  // base — i လုံး ဖျက်
        for (int j = 0; j <= n; j++) dp[0][j] = j;  // base — j လုံး ထည့်
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];     // တူ → ဘာမှ မလို
                } else {
                    dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],         // replace
                                   Math.min(dp[i - 1][j],            // delete
                                            dp[i][j - 1]));          // insert
                }
            }
        }
        return dp[m][n];
    }
}

၅။ 0/1 Knapsack

item n ခု — တစ်ခုစီမှာ အလေးချိန် weight[i] နဲ့ တန်ဖိုး value[i] ရှိ။ အိတ် (knapsack) က အလေးချိန် W ထိ ဆံ့။ item တစ်ခုကို ယူ ဒါမှမဟုတ် မယူ (၂ ပိုင်း မဖြတ်) ဆိုရင် — အိတ်ထဲ ထည့်လို့ ရတဲ့ တန်ဖိုး စုစုပေါင်း အများဆုံး ပြန်ပါ။

Input: weight = [1,3,4,5], value = [1,4,5,7], W = 7
Output: 9
   (item 1 (w3,v4) + item 2 (w4,v5) = အလေး 7, တန်ဖိုး 9)

ရှင်းလင်းချက်

ဒါက "budget အကန့်အသတ်နဲ့ value အများဆုံး" ပြဿနာ — dp[i][w] table နဲ့ ဖြေတယ်။

State: dp[i][w] = ပထမ i ခု item ထဲက ရွေးပြီး — အလေးချိန် w ထိ — တန်ဖိုး အများဆုံး။
Transition: item i အတွက် ၂ ရွေး —
- မယူ → dp[i-1][w] (အရင် item တွေ အတိုင်း)။
- ယူ (weight ဆံ့မှ — weight[i-1] <= w) → dp[i-1][w - weight[i-1]] + value[i-1]။
- ၂ ခုထဲက max → dp[i][w] = max(မယူ, ယူ)။
Base case: dp[0][*] = 0 (item မရှိ → တန်ဖိုး ၀)။

weight=[1,3,4,5], value=[1,4,5,7], W=7 — dp[i][w] table (နောက်ဆုံး dp[4][7] = 9) ဖြည့်သွားတယ်။

Time Complexity: $O(n \times W)$ - item × weight။
Space Complexity: $O(n \times W)$ - table (rolling array နဲ့ $O(W)$ လျှော့နိုင်)။

Java Solution

class Solution {
    public int knapsack(int[] weight, int[] value, int W) {
        int n = weight.length;
        int[][] dp = new int[n + 1][W + 1];        // row 0 = item မရှိ (base = 0)
        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= W; w++) {
                dp[i][w] = dp[i - 1][w];            // မယူ
                if (weight[i - 1] <= w) {          // ဆံ့မှ — ယူလို့ ရ
                    dp[i][w] = Math.max(dp[i][w],
                            dp[i - 1][w - weight[i - 1]] + value[i - 1]);  // ယူ
                }
            }
        }
        return dp[n][W];
    }
}