演算法筆記:動態規劃 Dynamic programming
為什麼上禮拜要學時間複雜度 O(2^n) 的遞迴呢?因為動態規劃可以解決重複解子問題的無效率部分。解決方法不難理解:把已經計算過的部分儲存下來!時間複雜度可以降低至O(n)
動態規劃適用情況
能採用動態規劃求解的問題的一般要具有3個性質:
1. 最優化原理:如果問題的最優解所包含的子問題的解也是最優的,就稱該問題具有最優子結構,即滿足最優化原理。
2. 無後效性:即某階段狀態一旦確定,就不受這個狀態以後決策的影響。也就是說,某狀態以後的過程不會影響以前的狀態,只與當前狀態有關。
3. 有重疊子問題:即子問題之間是不獨立的,一個子問題在下一階段決策中可能被多次使用到。(該性質並不是動態規劃適用的必要條件,但是如果沒有這條性質,動態規劃演算法同其他演算法相比就不具備優勢)
求解的基本步驟
動態規劃所處理的問題是一個多階段決策問題,一般由初始狀態開始,通過對中間階段決策的選擇,達到結束狀態。這些決策形成了一個決策序列,同時確定了完成整個過程的一條活動路線(通常是求最優的活動路線)。動態規劃的設計都有著一定的模式,一般要經歷以下幾個步驟:
初始狀態→│決策1│→│決策2│→…→│決策n│→結束狀態,動態規劃就像是遞迴一樣,必須給定邊界條件(終止條件)。
利用動態規劃解費氏數列
上樓梯的例子
動態規劃二維矩陣解題秘訣
動態規劃的題目不容易直接看題目寫出答案,可以先用大腦計算一次把矩陣寫下來,例如下圖的 path = [] ,再藉由圖形推敲出規則,最後寫出程式碼如下圖右方。此外,動態規劃經常要多製造一行跟一列的空值,例如 0 來顯示迴圈開始之前的狀態。例如 paths[1][2] = paths[0][2] + path[1][1] ,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/