/images/gravatar2.jpg

Steven Lin

理解Dynamic Programming 2 - 用 coin counting problem例子來了解

Coin Counting Problem - 依照幣種付錢問題 前言 🚀 🚀 🚀 Coin Counting Problem 就是遇到以下類似問題 - 假設我們有 1 c , 5 c , 10 c , 25 c,4種錢幣 (c => cents 美金的幾分錢 => 1 dollars = 100 cents) 今天我們要用這4種幣值,去付剛好31c,且使越少錢幣個數越好。 首先解決此問題的方法肯定不只一個答案,所以何謂optimal solution(最佳解)對我們來說就很重要 這個問題的optimal solution如題目所說,問題的最佳解必然是使用最少錢幣數量的解。 站在一般人腦角度思考 🚀 🚀 🚀 我們在腦中代入甚至直覺的得到一個答案 : 25c+5c+1c -> 一共三個硬幣是最佳解 但運作思維又是如何呢? 身為工程師,電腦科學家我們要透徹剖析想像計算機要如何思考! 站在計算機的角度思考 🚀 🚀 🚀 在這邊我們改個題目 假設我們有 1 c , 3 c , 4 c,3種錢幣

理解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(由下而上)的設計 - 先解決每一個小問題集合起來就是大問題的解決辦法 !