Introduction of Dynamic Programming

Programming လောကမှာ Dynamic Programming (DP) ဆိုတာ ကြားရင် developer တော်တော်များများအတွက် ခေါင်းရှုပ်စရာ ဖြစ်ကောင်းဖြစ်နိုင်ပါတယ်။ တကယ်တော့ သူ့ရဲ့ core idea က ရိုးရှင်းပါတယ်။ Complex problem တစ်ခုကို smaller problems တွေ ခွဲပြီး solve လုပ်ပါတယ်။ အဓိက trick က subproblems တွေရဲ့ results တွေကို မှတ်ထားခြင်းပါ။ တူညီတဲ့ subproblem ပြန်ကြုံရင် ပြန်မတွက်တော့ဘဲ သိမ်းထားတဲ့ answer ကို သုံးလိုက်ရုံပါပဲ။ ဒါက exponential time complexity ကို polynomial time အဖြစ် လျှော့ချပေးနိုင်ပါတယ်။

Problem မှာ characteristics နှစ်ခု ရှိရပါမယ်။ ပထမက optimal substructure ပါ။ Problem ရဲ့ solution က subproblems တွေရဲ့ solutions တွေကနေ တည်ဆောက်နိုင်ရမယ်။ ဒုတိယက overlapping subproblems ပါ။ တူညီတဲ့ subproblems တွေကို ထပ်ခါထပ်ခါ solve လုပ်ရတယ်။ ဒီနေရာမှာ Fibonacci က အကောင်းဆုံး နမူနာပါ။ F(n) = F(n-1) + F(n-2) ဆိုတဲ့ naive recursion ကိုကြည့်ရင် time complexity က O(2ⁿ) ဖြစ်လို့ နှေးပါတယ်။ ဘာကြောင့်လဲဆိုတော့ တူညီတဲ့ values တွေကို ထပ်ခါထပ်ခါ တွက်နေရလို့ပါ။ Results တွေကို memo dictionary မှာ cache လုပ်ထားလိုက်ရုံနဲ့ O(n) ဖြစ်သွားပါပြီ။

နမူနာအနေနဲ့ တောင်တက်တဲ့ climbing stairs ကို ကြည်လို့ရပါတယ်။ တောင်ထိပ််ကိုရောက်ဖို့ စုစုပေါင်းလှေကားထစ်အရေအတွက်ဟာ n ထစ်ရှိတယ် ဆိုကြပါစို့။ တစ်ကြိမ်ခြေလှမ်းရင် လှေကားထစ် တစ်ထစ် ဒါမှမဟုတ် နှစ်ထစ် တက်နိုင်တယ် ထားပါတော့။ တောင်ထိပ်ရောက်ဖို့ ပုံစံဘယ်နှစ်မျိုးနဲ့ တက်လို့ရနိုင်ပါမလဲ။ နားလည်သွားအောင် စုစုပေါင်းလှေကားထစ် အရေအတွက်ဟာ n=3 ဆိုရင် (1+1+1), (1+2), (2+1) ဆိုပြီး ပုံစံသုံးမျိုးနဲ့ တက်နိုင်ပါမယ်။ ဒါက ways(n) = ways(n-1) + ways(n-2) ဖြစ်သွားပြီး Fibonacci pattern ပဲ ပြန်ရပါတယ်။ စျေးဝယ်တဲ့အခါ ပြန်အမ်းငွေပေးတာကို ကြည့်ရင်လည်း ဒင်္ဂါး [1, 5, 10, 25] ဆိုပြီး အမျိုးအစားလေးခု ရှိတယ်။ 37 cents ပြန်ပေးဖို့ဆိုရင် coins အနည်းဆုံး ဘယ်နှစ်ခုလိုမှာပါလဲ။ 25+10+1+1 = 4 ခုပါ။ ဒါကို Git diff operations တွေမှာ file changes ကြည့်ဖို့ သုံးကြပါတယ်။ Practice လုပ်ချင်ရင် easy problems တွေကနေစပြီး တဖြည်းဖြည်း advance problems တွေရောက်အောင် လုပ်လို့ရပါတယ်။