動態規畫

網路上那麼多的動態規化教學，總是一大堆看不懂的東西，本篇先使用付款實例，進行不同的方式說明

付款實例

台灣的幣別有 1, 5, 10, 50, 100, 500, 1000 等 7 種幣別。

如果你消費了 987 元，那應該怎麼付錢，才能淘出最少數量的貨幣數量付給店家足夠的金額 ? 我們腦袋隨便一算，很容易的就知道要付 1 張 500 元，4 張 100 元，1 個 50元，3 個 10 元，1 個 5 元，2 個 1 元，總共是 1+4+1+3+1+2 = 12 個貨幣。

如果我們的貨幣 (狀態) 有上百種，那該如何用電腦算出最少的數量呢 ????
請特別注意，我們的要求，是如何付出最少的貨幣數量，當然金額一定要足夠。

思考邏輯

假設我們要付987元，那麼可以有如下選擇方案 — (付1元剩 986元)，(付5元剩 982元)，(付10元剩 977元)，(付50元剩 937元)，(付100元剩 887元)，(付500元剩 487元)，共六種方式。每一種付款方式，剩餘的金額分別為 (986, 982, 977, 937, 887, 487) ，而這些錢的付款最少次數以前就算過了(都是11次)。

所以就是(12,12,12,12,12,12)次，然後從這個集合中選取最小值。

上述 (986,982,977,937,887,487)  這些付款方式的最佳解，怎麼就以前就解過了呢? 原來是用 for 迴圈，從1塊錢，2塊錢，一直堆積上來，並儲存在記憶体中的。

總付款 : 987元
貨幣(一次)    剩餘         總共
1            986(11次)    11+1=12次
5            982(11次)    11+1=12次
10           977(11次)    11+1=12次
50           937(11次)    11+1=12次
100          887(11次)    11+1=12次
500          487(11次)    11+1=12次

實際代碼

底下是實際的完整代碼，最後顯示的結果是 12 種。

動態規畫，就是從舊有經驗所取得的最佳解，然後獲取未來的解法。

方格移動

在一個 m*n 的格子中，從左上角 (0, 0) 走到右下角 (m-1, n-1) 共有幾種方式呢。這邊有個規定，只能往右邊或往下面走，不可以斜著走，也不可以往上往左走。

上圖要走到黃色那格(1，1)，可能由 (0, 1) 往下走，也可能由(1, 0)往右走，所以要走到黃色格有2種方式。那要走到藍色那格有幾種方式呢，就是 (1, 1) 的2種方式+ (0,2) 的 1 種方式 = 3 種方式。

如此依序往右往下計算每一個，直到最右下角就是70種方式。

最大正方型面積

在一個 m*n 的格子中，1表示土地，0表示海洋，那麼如何計算最大的正方型土地面積呢? 下圖是矩陣的型狀。

>

底下是完整的程式碼

動態規畫其實是一門很深的課程，差不多需一學期(6個月)的時間來學習，裏面有很多的演算法可以應用。有興趣的人可以參考如下卡卡恩大神所寫的文章.

https://ithelp.ithome.com.tw/articles/10215363