什麼是 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