演算法筆記：動態規劃 Dynamic programming

為什麼上禮拜要學時間複雜度 O(2^n) 的遞迴呢？因為動態規劃可以解決重複解子問題的無效率部分。解決方法不難理解：把已經計算過的部分儲存下來！時間複雜度可以降低至O(n)

可以發現遞迴解費氏數列中 F(3) 出現兩次，F(2) 出現了三次，都是重複計算

動態規劃適用情況

能採用動態規劃求解的問題的一般要具有3個性質：
1. 最優化原理：如果問題的最優解所包含的子問題的解也是最優的，就稱該問題具有最優子結構，即滿足最優化原理。
2. 無後效性：即某階段狀態一旦確定，就不受這個狀態以後決策的影響。也就是說，某狀態以後的過程不會影響以前的狀態，只與當前狀態有關。
3. 有重疊子問題：即子問題之間是不獨立的，一個子問題在下一階段決策中可能被多次使用到。（該性質並不是動態規劃適用的必要條件，但是如果沒有這條性質，動態規劃演算法同其他演算法相比就不具備優勢）

求解的基本步驟

動態規劃所處理的問題是一個多階段決策問題，一般由初始狀態開始，通過對中間階段決策的選擇，達到結束狀態。這些決策形成了一個決策序列，同時確定了完成整個過程的一條活動路線(通常是求最優的活動路線)。動態規劃的設計都有著一定的模式，一般要經歷以下幾個步驟：
初始狀態→│決策１│→│決策２│→…→│決策ｎ│→結束狀態，動態規劃就像是遞迴一樣，必須給定邊界條件（終止條件）。

兩種動態規劃的解法

利用動態規劃解費氏數列

從 n 到 0 上到下的解法

從 0 到 n 下到上的解法

空間優化的解法，使用三個參數而非一個 new Array(n) 矩陣

上樓梯的例子

top down 利用 memo 紀錄算過的值

求經過的階梯數字總和最小

使用 a,b 變數紀錄最小的 cost，題目不需要列出整個陣列

動態規劃二維矩陣解題秘訣

動態規劃的題目不容易直接看題目寫出答案，可以先用大腦計算一次把矩陣寫下來，例如下圖的 path = [] ，再藉由圖形推敲出規則，最後寫出程式碼如下圖右方。此外，動態規劃經常要多製造一行跟一列的空值，例如 0 來顯示迴圈開始之前的狀態。例如 paths[1][2] = paths[0][2] + path[1][1] ，0 等於是邊界，沒有辦法抵達這裡。

先製造出邊界，一橫一豎設定值為 0

手寫矩陣可以更容易找到規律

參考資料：
1.https://codertw.com/%E7%A8%8B%E5%BC%8F%E8%AA%9E%E8%A8%80/586675/
2.https://codertw.com/%E7%A8%8B%E5%BC%8F%E8%AA%9E%E8%A8%80/586686/