Contents

理解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種錢幣

今天我們要用這3種幣值,去付剛好6c,且使越少錢幣個數越好。


先帶進Dynamic Programming觀念-拆解問題。

  • 若付1c => 1 個 coins

  • 若付2c => 2 個 coins (1c + 1c)

  • 若付3c => 1 個 coins

  • 若付4c => 1 個 coins

  • 若付5c

    => 2 個 coins(4c + 1c)

    => 3 個 coins(3c + 2c) = (3c +1c + 1c)

  • 所以付6c

    => 3 個 coins(1c + 5c) = (1c + 1c + 4c)

    => 3 個 coins(2c + 4c) = (1c + 1c + 4c)

    => 2 個 coins(3c + 3c)

  • 最後找到optimal solution 2


可能有些人看著上面的一行一行拆解問題的式子發現它可以化成tree的形式,如下圖

tree

大家有發現嗎 ❗ ❓ ❗ ❓ 圖中有許多一樣的block,看起來也有對稱的樣子

意味著 “電腦多做了很多重複的事” ❗ ❗ ❗

現在帶進Dynamic Programming之前所說的觀念 bottom-up

將大問題不斷向下拆解後,由下往上合併時,會把每一個小問題的答案存進一個Array裡,之後遇到相同問題時,會先到Array裡去找答案,節省掉許多的時間提昇許多的效能,例如: 上圖中的block(1,1),它是不存在幣種的2c拆解後的解答,故我們如果再遇到2c時就可以直接到Array裡找到它是2個coins(1c + 1c)


至此我們已經搞懂了Dynamic Programming的拆解問題也弄懂了大問題與小問題之間的關係,更清楚的了解bottom-up的運作。


接下來要來發展完整的Dynamic Programming,也就是將它的遞迴關係寫出來 ❗ ❗ ❗

  • 首先我們先定義一個Function C(k) => return 剛好付"k"cents所需要coins的最少數量

  • C(k) = min{C(i) + C(k-i)} => 每次都將問題切成兩個小問題,不斷的切直到底,再將它合併回來尋得答案

  • 一樣以上圖的例子來看,可以寫成

    C(6) = min{ C(1) + C(5), C(2) + C(4), C(3) + C(3)}

    由於,

    C(5) = min{ C(1) + C(4), C(2) + C(3)}

    C(2) = C(1) + C(1)

    所以,

    C(6) = min{ C(1) + min{ C(1) + C(4), C(1) + C(1) + C(3)}, C(1) + C(1) + C(4), C(3) + C(3)}

    代入 C(1)=C(3)=C(4)=1,

    C(6) = 2,Optimal Solution Gettttt ✅✅✅

(btw,這邊過程若有點陌生要去看一下Recurive的定義,實際trace一下執行的路徑會更能領悟喔❗❗)


結論 🚀 🚀 🚀

在這邊我們可以瞭解到當遇到真實問題時,發展Dynamic Programming的所需要做的分析,跟最後能得到的結果,雖然這個問題算是非常簡單,但當你藉由這個案例了解到Dynamic Programming所要傳遞的精神,便是邁出了相當一大步😎😎😎

最後再為大家重提一下運用Dynamic Programming的時機,先確定是否能用Divide and Conquer解,可以的話再嘗試用Dynamic Programming去解(其實很多能用DP去解的問題,也能用Greedy Algorithm 貪婪演算法且更快,之後會在Greedy Algorithm series解釋)。


最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!


➔ 下一篇會帶來另一個Dynamic Programming案例 - 連續矩陣相乘