အခန်း ၂၂ - 1-D Dynamic Programming

အခန်း ၂၀ (Greedy) မှာ — အကြွေစေ့ [1,3,4] နဲ့ 6 ဖွဲ့တဲ့အခါ greedy က 4+1+1 (၃ စေ့) ဆိုပြီး မှားသွားတာ တွေ့ခဲ့ပါတယ် (အမှန် 3+3 = ၂ စေ့)။ "အခု အကောင်းဆုံး" ရွေးတာ မလုံလောက်တဲ့ — ဒီလို ပြဿနာတွေကို ဖြေဖို့ — ဖြစ်နိုင်ခြေ အကုန် စစ်ဖို့ လိုတယ်။ ဒါပေမယ့် အကုန် brute-force စစ်ရင် — တူညီတဲ့ အလုပ်ကို ထပ်ခါထပ်ခါ လုပ်မိပြီး အလွန် နှေးတယ်။

Dynamic Programming (DP) က ဒီပြဿနာကို ဖြေတယ် — "ထပ်တူ ပြဿနာငယ်တွေရဲ့ အဖြေကို တစ်ခါတည်း တွက်ပြီး သိမ်းထား၊ ပြန်လိုရင် ပြန်သုံး" ဆိုတဲ့ idea ပါ။ DP ဟာ beginner အများစုအတွက် အခက်ဆုံး topic လို့ ဆိုကြပေမယ့် — တကယ်တော့ recursion → memoization → tabulation ဆိုတဲ့ flow အတိုင်း တစ်ဆင့်ချင်း လိုက်သွားရင် — အလွန် စနစ်ကျတဲ့ pattern တစ်ခုသာ ဖြစ်ပါတယ်။ ဒီအခန်းမှာ အဲ့ဒီ flow ကို Fibonacci နဲ့ စတင်ပြီး — classic ပြဿနာ ၅ ခုနဲ့ လေ့လာသွားပါမယ်။

DP ဆိုတာ ဘာလဲ — ဘယ်တော့ သုံးလဲ

ပြဿနာတစ်ခုကို DP နဲ့ ဖြေလို့ ရဖို့ — အင်္ဂါရပ် ၂ ခု ရှိရတယ် —

၁။ Overlapping Subproblems (ထပ်တူ ပြဿနာငယ်)

ပြဿနာကြီးကို ပြဿနာငယ်တွေ ခွဲဖြေတဲ့အခါ — တူညီတဲ့ ပြဿနာငယ် ကို အကြိမ်ကြိမ် ပြန်ဖြေနေရတယ်။ Fibonacci ($F(n) = F(n-1) + F(n-2)$) ကို ကြည့်ရအောင် —

graph TD
    F5(("F(5)")) --> F4(("F(4)"))
    F5 --> F3a(("F(3)"))
    F4 --> F3b(("F(3)"))
    F4 --> F2a(("F(2)"))
    F3a --> F2b(("F(2)"))
    F3a --> F1a(("F(1)"))
    F3b --> F2c(("F(2)"))
    F3b --> F1b(("F(1)"))
    F2c --> F1c(("F(1)"))
    F2c --> F0a(("F(0)"))

    classDef dup stroke:#e03131,stroke-width:3px,color:#e03131;
    class F3a,F3b,F2a,F2b,F2c dup;

→ F(3) ၂ ခါ၊ F(2) ၃ ခါ ... ထပ်တွက်နေ (ပြောင်းရောင် = ထပ်တူ ပြဿနာငယ်)

F(2) တို့ F(3) တို့ကို ထပ်ခါထပ်ခါ တွက်နေတာ — ဒါ overlapping subproblem ပါ။ ဒီအဖြေတွေ သိမ်းထားရင် တစ်ခါပဲ တွက်ရတော့မယ်။

၂။ Optimal Substructure (အကောင်းဆုံး ဖွဲ့စည်းပုံ)

ပြဿနာကြီးရဲ့ အကောင်းဆုံး အဖြေဟာ — ပြဿနာငယ်တွေရဲ့ အကောင်းဆုံး အဖြေတွေကနေ တည်ဆောက်လို့ ရတယ်။ ဥပမာ — "n ထစ် တက်ဖို့ နည်းလမ်း အရေအတွက်" က — "n-1 ထစ်" နဲ့ "n-2 ထစ်" ရဲ့ အဖြေတွေ ပေါင်းတာပဲ။

ဒီ ၂ ခု ရှိရင် — DP သုံးလို့ ရတယ်။ (greedy နဲ့ ကွာတာက — greedy မှာ optimal substructure ရှိပေမယ့် "တစ်ခုတည်း ရွေး"တာ၊ DP မှာ "ဖြစ်နိုင်ခြေ အကုန် စစ်ပြီး အကောင်းဆုံး ယူ"တာ)။

DP ၃ ဆင့် — Recursion → Memoization → Tabulation

DP ပြဿနာ တစ်ခုကို ဖြေတဲ့အခါ — အဆင့် ၃ ဆင့်နဲ့ တိုးတက်အောင် လုပ်သွားတာက အကောင်းဆုံး လမ်းကြောင်းပါ။ Fibonacci နဲ့ ကြည့်ရအောင်။

အဆင့် ၁ — Plain Recursion (နှေး)

ပြဿနာကို တိုက်ရိုက် recursion နဲ့ ရေးတာ — မှန်ပေမယ့် overlapping subproblem ကြောင့် exponential $O(2^n)$ — အလွန် နှေး။

int fib(int n) {
    if (n <= 1) return n;                   // base case
    return fib(n - 1) + fib(n - 2);         // ထပ်တူ ပြဿနာငယ် ထပ်တွက်
}

အဆင့် ၂ — Memoization (Top-down + Cache)

recursion ကို ထားပြီး — တွက်ပြီးသား အဖြေကို cache (memo) ထဲ သိမ်း၊ ပြန်လိုရင် ပြန်သုံး။ ဒါနဲ့ ပြဿနာငယ် တစ်ခုကို တစ်ခါပဲ တွက်ရတော့လို့ — $O(n)$ ဖြစ်သွားတယ်။ ("top-down" — ပြဿနာကြီးကစ ဆင်းဖြေတာ)။

int fib(int n, int[] memo) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];       // တွက်ပြီးသား → ပြန်သုံး
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);  // တွက်ပြီး သိမ်း
    return memo[n];
}

အဆင့် ၃ — Tabulation (Bottom-up + Array)

recursion ဖျောက်ပြီး — ပြဿနာငယ်ကစ (base case ကစ) array dp[] ကို တဖြည်းဖြည်း ဖြည့်တက်တာ။ "bottom-up" — အသေးကစ အကြီးဆီ။ recursion stack မလိုလို့ stack overflow ရှောင်နိုင်ပြီး၊ ပိုမြန်တယ်။

int fib(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[0] = 0; dp[1] = 1;                    // base case
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];       // transition
    }
    return dp[n];
}

   dp ဖြည့်ပုံ (n=6):
   dp[0]=0  dp[1]=1  dp[2]=1  dp[3]=2  dp[4]=3  dp[5]=5  dp[6]=8
            └──────── dp[i] = dp[i-1] + dp[i-2] ────────┘

အဆင့် ၄ (bonus) — Space Optimization

dp[i] က dp[i-1] နဲ့ dp[i-2] ၂ ခုပဲ လိုတာမို့ — array တစ်ခုလုံး မလိုဘဲ variable ၂ ခုနဲ့ ရတယ် — space $O(n) → O(1)$။

int fib(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

မှတ်ရန်: Memoization (top-down) နဲ့ Tabulation (bottom-up) ၂ ခုလုံး $O(n)$ ပါ — ရွေးချယ်မှု ပဲ။ Recursion နဲ့ စဉ်းစားရ လွယ်ရင် memoization၊ stack overflow / speed အရေးကြီးရင် tabulation။ ဒီအခန်းက ပြဿနာ အများစုကို tabulation (1-D array) နဲ့ ပြသွားပါမယ်။

DP ရေးနည်း Framework — State, Transition, Base Case

DP ပြဿနာ တိုင်းကို ဖြေဖို့ — အောက်က မေးခွန်း ၃ ခု ဖြေနိုင်ရင် ပြီးပါပြီ —

1. State (dp[i] ဆိုတာ ဘာကို ကိုယ်စားပြုလဲ) — ဥပမာ "dp[i] = index i ထိ အကောင်းဆုံး အဖြေ"။ ဒါက အခက်ဆုံး အပိုင်း — state မှန်အောင် သတ်မှတ်နိုင်ရင် ကျန်တာ လွယ်သွားတယ်။
2. Transition (dp[i] ကို အရင် state တွေကနေ ဘယ်လို တွက်လဲ) — ဥပမာ dp[i] = dp[i-1] + dp[i-2]။ ဒါက DP ရဲ့ "ဆက်စပ်မှု ပုံသေနည်း"။
3. Base case (အသေးဆုံး state ရဲ့ တန်ဖိုး) — ဥပမာ dp[0] = 0, dp[1] = 1။ recursion ရပ်တဲ့ နေရာ။

ဒီ framework ကို ပြဿနာ ၅ ခုမှာ ထပ်ခါ သုံးသွားပါမယ် — state ရှာ၊ transition ရေး၊ base case သတ်မှတ်။

Real-world Examples

• Best Reward / Points — အဆင့်ဆင့် ဆုံးဖြတ်ချက် (ဥပမာ — "ဒီ level ကို ယူရင် reward + ၊ ဒါပေမယ့် နောက် level skip") မှာ — အကောင်းဆုံး စုစုပေါင်း reward တွက်တာ (House Robber pattern)။
• Retry / Cost Optimization — operation တစ်ခုစီ retry cost မတူရင် — "အနည်းဆုံး ကုန်ကျမှုနဲ့ အဆုံးထိ ရောက်ဖို့" အဆင့်ဆင့် တွက်တာ (Coin Change / Min Cost pattern)။
• Step-by-step Decision — "ဒီအဆင့်မှာ ဘယ် option ရွေးရင် နောက်ဆုံး အကောင်းဆုံးလဲ" ဆိုတဲ့ planning — ယခင် ဆုံးဖြတ်ချက်ရဲ့ ရလဒ်ကို သိမ်းပြီး ဆက်တွက်တာ။
• Text / Message Parsing — SMS / code ကို decode လုပ်တဲ့အခါ "ဖြစ်နိုင်တဲ့ နည်းလမ်း ဘယ်နှ ခု" တွက်တာ (Decode Ways)။
• Analytics — transaction stream မှာ "အမြတ်အများဆုံး ရတဲ့ ဆက်တိုက် ကာလ" ရှာတာ (Maximum Subarray)။

Questions

DP ပြဿနာ ဖြေတဲ့အခါ — အရင်ဆုံး state (dp[i] ဘာလဲ) သတ်မှတ်၊ ပြီးမှ transition နဲ့ base case ရှာတာပါ။ classic ၅ ခု ဖြေကြည့်ရအောင်။

၁။ Climbing Stairs

လှေကားမှာ n ထစ် ရှိ — တစ်ခါ ၁ ထစ် ဒါမှမဟုတ် ၂ ထစ် တက်နိုင်။ ထိပ်ဆုံး (n) ထိ တက်ဖို့ ကွဲပြားတဲ့ နည်းလမ်း ဘယ်နှ မျိုး ရှိလဲ။

Input: n = 3
Output: 3
   (1+1+1 ;  1+2 ;  2+1  → ၃ နည်း)

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

• State: dp[i] = ထစ် i ထိ တက်နိုင်တဲ့ နည်းလမ်း အရေအတွက်။
• Transition: ထစ် i ကို — ထစ် i-1 ကနေ (၁ ထစ်) ဒါမှမဟုတ် ထစ် i-2 ကနေ (၂ ထစ်) ရောက်နိုင်လို့ → dp[i] = dp[i-1] + dp[i-2]။ (Fibonacci နဲ့ တူ!)
• Base case: dp[0] = 1 (ဘာမှ မတက်ဘဲ ၁ နည်း)၊ dp[1] = 1။

n = 3 ကို လိုက်ကြည့်ရအောင် —

   dp[0]=1   dp[1]=1
   dp[2] = dp[1]+dp[0] = 1+1 = 2
   dp[3] = dp[2]+dp[1] = 2+1 = 3   ✓

Time Complexity: $O(n)$ - ထစ်တစ်ခုစီ တစ်ခါ။
Space Complexity: $O(1)$ - variable ၂ ခုပဲ (space optimized)။

Java Solution

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        int prev2 = 1, prev1 = 2;              // dp[1]=1, dp[2]=2
        for (int i = 3; i <= n; i++) {
            int cur = prev1 + prev2;           // dp[i] = dp[i-1] + dp[i-2]
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

၂။ House Robber

အိမ်တန်း nums — အိမ်တစ်လုံးစီမှာ ပိုက်ဆံ nums[i] ရှိ။ ဒါပေမယ့် ကပ်လျက် အိမ် ၂ လုံး ဖောက်ရင် alarm မြည်တယ်။ alarm မမြည်စေဘဲ — ပိုက်ဆံ အများဆုံး ဘယ်လောက် ရနိုင်လဲ။

Input: nums = [2,7,9,3,1]
Output: 12
   (အိမ် 0 (2) + အိမ် 2 (9) + အိမ် 4 (1) = 12 ;  ကပ်လျက် မဖောက်)

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

• State: dp[i] = အိမ် 0..i ထဲက ဖောက်လို့ ရတဲ့ ပိုက်ဆံ အများဆုံး။
• Transition: အိမ် i အတွက် ရွေးချယ်စရာ ၂ ခု — (၁) မဖောက် → dp[i-1] (အရင်အထိ အကောင်းဆုံး)၊ (၂) ဖောက် → dp[i-2] + nums[i] (ကပ်လျက် မဖြစ်အောင် i-1 ကျော်)။ ၂ ခုထဲက max ယူ → dp[i] = max(dp[i-1], dp[i-2] + nums[i])။
• Base case: dp[0] = nums[0]၊ dp[1] = max(nums[0], nums[1])။

nums = [2,7,9,3,1] ကို လိုက်ကြည့်ရအောင် —

   i   nums[i]   dp[i-1]   dp[i-2]+nums[i]    dp[i] = max
   0     2        —          —                2
   1     7        2          —                max(2,7)        = 7
   2     9        7          2+9=11           max(7,11)       = 11
   3     3        11         7+3=10           max(11,10)      = 11
   4     1        11         11+1=12          max(11,12)      = 12  ✓

Time Complexity: $O(n)$။
Space Complexity: $O(1)$ - variable ၂ ခု (space optimized)။

Java Solution

class Solution {
    public int rob(int[] nums) {
        int prev2 = 0, prev1 = 0;              // dp[i-2], dp[i-1]
        for (int num : nums) {
            int cur = Math.max(prev1, prev2 + num);  // မဖောက် vs ဖောက်
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

၃။ Coin Change

အကြွေစေ့ အမျိုးအစား coins (အကန့်အသတ်မဲ့ အရေအတွက်) နဲ့ ပမာဏ amount ပေးထားသည်။ amount ဖွဲ့ဖို့ အကြွေစေ့ အရေအတွက် အနည်းဆုံး ပြန်ပါ။ မဖွဲ့နိုင်ရင် -1။

Input: coins = [1,3,4], amount = 6
Output: 2
   (3 + 3 = 6  → ၂ စေ့ ;  greedy ရဲ့ 4+1+1=၃ စေ့ ထက် ပိုကောင်း)

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

ဒါက အခန်း ၂၀ မှာ greedy ကျိုးခဲ့တဲ့ ပြဿနာပါ — DP နဲ့ ဖြေရင် မှန်တယ် (ဖြစ်နိုင်ခြေ အကုန် စစ်လို့)။

• State: dp[a] = ပမာဏ a ဖွဲ့ဖို့ အကြွေစေ့ အနည်းဆုံး။
• Transition: coin c တစ်ခုစီအတွက် — a ကို ဖွဲ့ဖို့ "coin c ယူပြီး ကျန် a-c ဖွဲ့" → dp[a] = min(dp[a], dp[a-c] + 1)။
• Base case: dp[0] = 0 (ပမာဏ ၀ ဖွဲ့ဖို့ ၀ စေ့)။ ကျန်တာ ∞ (မဖွဲ့နိုင်သေး) နဲ့ စ။

coins = [1,3,4], amount = 6 ကို dp ဖြည့်ကြည့်ရအောင် —

   a:     0   1   2   3   4   5   6
   dp:    0   1   2   1   1   2   2
                          ↑       ↑
   dp[3] = dp[0]+1 = 1  (coin 3)
   dp[6] = min(dp[5]+1, dp[3]+1, dp[2]+1) = min(3, 2, 3) = 2  (coin 3)  ✓

Time Complexity: $O(amount \times coins)$ - ပမာဏ တစ်ခုစီ × coin တစ်ခုစီ။
Space Complexity: $O(amount)$ - dp array။

Java Solution

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);           // "∞" အစား — ဘယ်တော့မှ မရောက်နိုင်တဲ့ ကြီးတန်
        dp[0] = 0;                             // base case
        for (int a = 1; a <= amount; a++) {
            for (int c : coins) {
                if (c <= a) {                  // coin က ပမာဏထက် မကြီးမှ
                    dp[a] = Math.min(dp[a], dp[a - c] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];  // မရောက်ရင် -1
    }
}

၄။ Maximum Subarray (Kadane's Algorithm)

integer array nums (အနုတ် ပါ) ပေးထားသည်။ ဆက်တိုက် subarray (အနည်းဆုံး ၁ ခု) ထဲက — ပေါင်းလဒ် အများဆုံး ပြန်ပါ။

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
   (subarray [4,-1,2,1] ရဲ့ ပေါင်းလဒ် = 6)

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

• State: dp[i] = index i မှာ ဆုံးတဲ့ subarray ရဲ့ ပေါင်းလဒ် အများဆုံး။
• Transition: index i မှာ ဆုံးတဲ့ အကောင်းဆုံး subarray က — (၁) nums[i] တစ်ခုတည်း အသစ်စ၊ (၂) အရင် subarray (dp[i-1]) ကို ဆက်ပြီး nums[i] ပေါင်း — ၂ ခုထဲက max → dp[i] = max(nums[i], dp[i-1] + nums[i])။ (dp[i-1] က နုတ်ဖြစ်နေရင် — ဆက်တာ နစ်နာလို့ အသစ်စ ပိုကောင်း)။
• Base case: dp[0] = nums[0]။ answer က dp[] အကုန်ရဲ့ max (နောက်ဆုံး dp မဟုတ်)။

[-2,1,-3,4,-1,2,1,-5,4] ကို လိုက်ကြည့်ရအောင် —

   nums:   -2   1   -3   4   -1   2   1   -5   4
   dp:     -2   1   -2   4    3   5   6    1   5
                             └─────────┘
   dp[i] = max(nums[i], dp[i-1]+nums[i])
   global max = 6  (dp[6])  ✓

Time Complexity: $O(n)$ - တစ်ခေါက်ပဲ ဖြတ်။
Space Complexity: $O(1)$ - cur နဲ့ best ၂ ခုပဲ (space optimized)။

Java Solution

class Solution {
    public int maxSubArray(int[] nums) {
        int cur = nums[0], best = nums[0];     // dp[0] = nums[0]
        for (int i = 1; i < nums.length; i++) {
            cur = Math.max(nums[i], cur + nums[i]);  // အသစ်စ vs ဆက်
            best = Math.max(best, cur);        // global max
        }
        return best;
    }
}

၅။ Decode Ways

'A'→"1", 'B'→"2", ..., 'Z'→"26" ဆိုတဲ့ mapping နဲ့ — ဂဏန်း string s ကို ပေးထားသည်။ s ကို စာလုံး အဖြစ် decode လုပ်နိုင်တဲ့ နည်းလမ်း ဘယ်နှ မျိုး ရှိလဲ ပြန်ပါ။ ('0' က သီးသန့် စာလုံး မရှိ — 10, 20 အဖြစ်သာ)။

Input: s = "226"
Output: 3
   ("2 2 6"=BBF ;  "22 6"=VF ;  "2 26"=BZ  → ၃ နည်း)

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

• State: dp[i] = string ရဲ့ ပထမ i လုံး (s[0..i-1]) ကို decode လုပ်နိုင်တဲ့ နည်းလမ်း အရေအတွက်။
• Transition: လုံး i အတွက် — (၁) s[i-1] က '0' မဟုတ်ရင် (၁ လုံး တစ်ခုတည်း 1..9) → dp[i] += dp[i-1]၊ (၂) s[i-2..i-1] က 10..26 ကြားဆို (၂ လုံး တွဲ) → dp[i] += dp[i-2]။
• Base case: dp[0] = 1 (string ဗလာ — ၁ နည်း)၊ dp[1] = (s[0] != '0') ? 1 : 0။

s = "226" ကို လိုက်ကြည့်ရအောင် —

   dp[0] = 1  (ဗလာ)
   dp[1] = 1  ("2" → B)
   dp[2]:  "2" (≠0) → += dp[1]=1 ;  "22" (10..26) → += dp[0]=1  → dp[2]=2
   dp[3]:  "6" (≠0) → += dp[2]=2 ;  "26" (10..26) → += dp[1]=1  → dp[3]=3  ✓

Time Complexity: $O(n)$ - လုံးတစ်ခုစီ တစ်ခါ။
Space Complexity: $O(1)$ - variable ၂ ခု (space optimized)။

Java Solution

class Solution {
    public int numDecodings(String s) {
        if (s.charAt(0) == '0') return 0;      // '0' နဲ့ စ → decode မရ
        int prev2 = 1, prev1 = 1;              // dp[0]=1, dp[1]=1
        for (int i = 2; i <= s.length(); i++) {
            int cur = 0;
            if (s.charAt(i - 1) != '0') cur += prev1;          // ၁ လုံး (1..9)
            int two = Integer.parseInt(s.substring(i - 2, i)); // ၂ လုံး တွဲ
            if (two >= 10 && two <= 26) cur += prev2;          // (10..26)
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}