Dynamic Programming — Overlapping Subproblems ကို Memoization/Tabulation နဲ့ ဖြေရှင်းခြင်း

နားလည်ထားရမယ့် အချက်

Dynamic programming က property နှစ်ခုရှိတဲ့ problem အတွက် အသုံးဝင်တယ် — optimal substructure (problem တစ်ခုလုံးရဲ့ best solution ကို subproblem တွေရဲ့ best solution ကနေ တည်ဆောက်ရတာ) နဲ့ overlapping subproblems (subproblem တွေက distinct မဟုတ်ဘဲ ထပ်ခါထပ်ခါ ပေါ်နေတာ) ပါ။ Naive recursive Fibonacci ဟာ ဒီနှစ်ခုစလုံးရှိပေမယ့် overlap ကို ignore လုပ်ရင် ဘာဖြစ်နိုင်လဲဆိုတာ ဖော်ပြတဲ့ textbook ဥပမာပါ — fib(n) က fib(n-1) နဲ့ fib(n-2) ကို ခေါ်တယ်၊ fib(n-1) ကိုယ်တိုင်ကလည်း fib(n-2) နဲ့ fib(n-3) ကို ခေါ်တယ်၊ fib(n-2) ဆိုတာကို branch နှစ်ခုစလုံးက independent ဖြစ်ဖြစ် compute လုပ်နေကြတယ်။ ဒီ redundancy က recursive ဖြစ်ဖြစ် ပေါင်းစပ်သွားလို့ total call count က exponential ဖြစ်ကာ O(2^n) ဖြစ်လာတယ် — fib(40) ကို naive method နဲ့ compute လုပ်ရင် calculator တစ်ခုက ချက်ချင်း ထုတ်ပေးနိုင်တဲ့ number တစ်ခုအတွက် redundant call ဘီလီယံတစ်ခုကျော် ကုန်ကျရမယ်။ ဖြေရှင်းနည်းက fib(k) ဆိုတာ call path ဘယ်ဟာကနေ ရောက်ရောက် value တူတူပဲဆိုတာ သတိထားမိတာပါ — ဒါကြောင့် တစ်ကြိမ်ပဲ compute ဖို့ လိုတယ်။ Memoization က top-down နည်းနဲ့ ဒါကို လုပ်တယ် — natural recursive structure ကို ဆက်ထားပြီး result တစ်ခုစီကို input အလိုက် dict ထဲ cache ထားကာ ပြန်ချင်တိုင်း cache ကို ဦးစွာ check လုပ်တယ်။ Tabulation ကတော့ bottom-up နည်းနဲ့ လုပ်တယ် — fib(0) နဲ့ fib(1) ကနေစပြီး fib(n) အထိ array တစ်ခုကို iteratively တည်ဆောက်တယ်၊ recursion လုံးဝမလိုဘူး။ နှစ်ခုစလုံးက redundant recomputation ကို ဖယ်ရှားပေးလို့ cost က O(n) ကျသွားတယ်။

လက်တွေ့ scenario နဲ့ ချိတ်ကြည့်မယ်

Tutorial Platform ရဲ့ 'prerequisite အားလုံးကို covers လုပ်တဲ့ shortest learning path' problem က dynamic programming နဲ့ natural fit ပါ — prerequisite dependency အားလုံးကို ဖြည့်ဆည်းတဲ့ goal တစ်ခုဆီ minimum-lesson-count path ကို compute လုပ်တာမှာ overlapping subproblem ရှိတယ် — lesson X ဆီ optimal path ကို နောက်ပိုင်း lesson အများကြီးရဲ့ optimal path prefix အနေနဲ့ ပြန်သုံးလေ့ရှိတယ်၊ fib(n) နဲ့ fib(n-1) နှစ်ခုစလုံးက fib(n-2) ကို ပြန်သုံးသလိုပါပဲ။ ဒီ overlap ကို ignore ပြီး goal lesson တိုင်းအတွက် best prerequisite chain ကို အစကနေ ပြန်တွက်နေရင် topic graph ကြီးလာတာနဲ့အမျှ exponential ကုန်ကျစရိတ် တက်လာမှာပါ။ Lesson တစ်ခုစီရဲ့ ဖြေရှင်းပြီးသား 'prerequisite ဖြည့်ဆည်းပြီး ဒီနေရာအထိ minimum lesson count' result ကို cache ထားတာ — memoization ရဲ့ approach အတိအကျပါပဲ — ဒါက intractable brute-force search တစ်ခုကို path request တိုင်းမှာ run လို့ရအောင် fast ပြီး lesson count နဲ့ linear ဖြစ်တဲ့ computation တစ်ခုအဖြစ် ပြောင်းပေးတယ်။

• Dynamic programming က optimal substructure နဲ့ overlapping subproblems ရှိတဲ့ problem မှာ အသုံးဝင်တယ်။
• Naive recursive Fibonacci က subproblem တွေကို ထပ်ခါထပ်ခါ ပြန်တွက်နေလို့ O(2^n) exponential ဖြစ်တယ်။
• Memoization (top-down cache) နဲ့ tabulation (bottom-up array) နှစ်ခုစလုံးက redundant work ကို ဖယ်ရှားပြီး O(n) အထိ ပြင်ပေးတယ်။

အတူတူ စမ်းရေးကြည့်မယ်

def fib_naive(n):
    if n < 2:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)  # recomputes the same subproblems repeatedly

def fib_memo(n, cache={}):
    if n < 2:
        return n
    if n not in cache:
        cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]

print(fib_naive(20))   # O(2^n): fine for small n, but blows up fast
print(fib_memo(60))    # O(n): each subproblem solved and cached exactly once

ပထမ line မှာ fib_naive(20) ရဲ့ result 6765 ကို print ထုတ်ပြီး၊ ဒုတိယ line မှာ fib_memo(60) ရဲ့ result 1548008755920 ကို instantly print ထုတ်မည် (naive method ဆိုရင် n=60 အတွက် လက်တွေ့ run လို့မရတော့ဘူး)။

Wikipedia — Dynamic programming — Data Structures & Algorithms