什麼是Dynamic Programming動態規劃?如何使用它?

DP經常被用來尋找最短路徑,minimize or maximize something

It’s a kind of exhaustive search => But it’s always lead to exponential time

if you use dynamic programming, it’s just lead polynomial time

There’s one perspective that DP is approximately careful brute force(kind of funny commination)

如果你查網路文章,都只會強調這句「計算並儲存小問題的解,並將這些解組合成大問題的解。」

說的簡單,但就是做不出來QQ

這篇就用人類聽得懂的語言來解釋看看Dynamic Programming動態規劃

什麼時機要想到Dynamic Programming動態規劃?

在解題時,我們都會參考某些特定環節使用相對應的解法,Dynamic也有它適用的場合:

  1. 可以拆成很多小問題
  2. 答案可以透過組合小問題來解
  3. 小問題重覆量很高

遞迴(Recursion) 跟遞迴關係(Recurrence Relation) 對我來說是兩個不一樣的東西。

遞迴 vs 動態規劃

我的理解是這樣的:動態規劃是一種設計演算法的範型(Paradigm),而遞迴是用來實現題解的一種手段(Implementation)。

只要滿足:一個問題可以拆成很多子問題,而這個問題的答案可以透過組合子問題的答案來得到它、再加上子問題的重複量很大,那麼這個問題就可以使用「把算過的東西記下來,以後會用得上」這個策略來設計演算法,而依循這個策略設計出來的演算法基本上就是動態規劃了。

至於要怎麼實作它,可以用遞迴(發現即將要使用的子問題還沒算過,就 call 一次自己然後把計算的結果存下來)、也可以不需要透過遞迴(比方說採用迴圈建表)。
所以,在某些題目條件下,我們可以使用遞迴來實作動態規劃演算法~

遞迴關係 vs 動態規劃

遞迴關係是指把問題與子問題連結起來的那個表達式,可以把它想像成公式那樣,只告訴你解是什麼,但沒指定要用什麼演算法來計算出這個解~但好處是,遞迴關係(包含遞迴終止條件)只要定義清晰,就可以設計出動態規劃(或分而治之)的演算法了。

Leave a Comment

發佈留言必須填寫的電子郵件地址不會公開。