Contents

理解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”

我們峰頂見!!!


➔ 下一篇會來實際跟著這個步驟解決真實問題 Coin Counting Problem