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

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

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

動態規劃適用情況

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

求解的基本步驟

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

兩種動態規劃的解法

利用動態規劃解費氏數列

從 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/

Share on facebook
Facebook
Share on linkedin
LinkedIn
Share on twitter
Twitter

More to explorer

Close Menu