理解Dynamic Programming 1 - 將定義化繁為簡

什麼是 Dynamic Programming !?
前言 🚀 🚀 🚀
“Programming” means planning, decision making and “Dynamic” means multistage, time-varying, … by Richard Bellman
其實就字面來看可以翻譯成動態規劃? 但是其實重點可以放在 “規劃” 大家可以不用在 “動態” 這個字去琢磨,它名字的來由其實也是一段故事~ 之後可以另外發一篇分享一下 ! 😄
那何謂 “規劃” 呢 ? 可以參考一下大學的基礎演算法的聖經本 “Introduction to Algorithms” written by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
Dynamic Programming Algorithm 是屬於 Divide and Conquer 的一種, 跟 Merge sort , Quick sort … 等 一樣, 是一種 Bottom-up(由下而上)的設計 - 先解決每一個小問題集合起來就是大問題的解決辦法 !!!
重點 🚀 🚀 🚀
Dyamic Programming 不像是 “一般演算法 " 有標準的 pesudo code , 我更願意將它說成是一種 “策略”
That is, 當我們要用Dynamic Programming去解決問題時,實際上是用它所定義的思考步驟去一步一步實行且解決問題。 ✅ ✅ ✅
先記住三個特性 (不知道有什麼用沒關係,後面會更白話的闡述)
- Planning
- Decision Making
- Multistage
首先這種 "策略" 讓你在遇到問題時可以依照它定義的step去逐步的解決問題 - 並發展出"這個問題的 Dynamic Programming Algorithm"
step 1 : ✅
Characterize the structure of an optimal solution. 也就是釐清整個問題的架構,將它拆成小問題,找到每個同樣小問題的最佳解之間的關係,大問題與小問題最佳解之間的關係 (這邊很抽象,但沒關係在下一篇講解實際問題時就會清楚明瞭了)。
step 2 : ✅
Recursively define the value of an optimal solution. 把在step 1釐清的架構寫成recursively遞迴關係 (一樣會在下一篇會講解定義實際問題的recursively relation)。
step 3 : ✅
Compute the value of an optimal solution in a bottom-up fashion. 將問題由下往上算出來,集合每一個小問題的解合併向上得到大問題的解。
step 4 : ✅
Construct an optimal solution from computed information. 其實可以併在step 3裡,也就是說最後得到大問題的解。
結論 🚀 🚀 🚀
1. 我們可以瞭解到實際上Dynamic Programming不是真的固定的一種演算法,而是提供給我們解決問題的思考與實作模板。
2. 當我們遇到問題時,可以先思考這個問題能否用Divide and Conquer的方式來解(其實就是能否切開問題逐個擊破,且能將很好的再合併起來),再嘗試用Dynamic Programming的思考與實作步驟去解決問題!!!
OK ! 至此希望幫助大家突破迷思,達成初步窺探與了解對於這個最捉摸不定的一個演算法!!!
最後祝福努力認真的各位 “All you dream of are hidden in your daily life”
我們峰頂見!!!