究竟什麼是 動態規劃DP?

小松鼠-avatar-img
發佈於演算法題目解析 個房間
更新於 發佈於 閱讀時間約 4 分鐘


動態規劃Dynamic Programming其實是
一種泛用的演算法思考方式演算法建構框架

動態規劃並不拘束於只能解課本上特定的的範例題。


只要我們能找出DP狀態定義、DP遞迴結構、初始條件(終止條件),就能適用動態規劃來解題,以數學的形式表達,並且在紙筆上或者電腦上、計算機上計算得到答案


最直接白話的解釋

白話的說,其實DP動態規劃就是一種問題化簡的技巧
幫助我們把大規模的題目化簡到小規模的題目解開小題目的解,把小題目的解儲存起來避免重複計算,並且由小規模的題目反推大規模題目的答案,最終得到原本大規模題目的解


就好像一句成語說的:「大事化小,小事化無。」
大問題化簡到小問題 就好比 大事化小
小問題透過查表或者初始條件得到答案,就相當於 小事化無


(犧牲)空間換取時間(進步)的策略

敏銳的讀者可能已經發現,DP的外表其實和DFS形式實現的遞迴function很像。

但是具體差別在哪裡呢?

DP同樣也有遞迴定義,但是多了隨身記事本
(課本會把隨身記事本稱之為DP table, 或 memoization記憶化的搜索)


DP = Recursion definition 遞迴定義 + Table 紀錄答案的表格

相當於 DFS + memoization


DP動態規劃演算法在遞迴的過程中,
會把每一次當下計算到的答案連同傳入參數一起存起來
這樣當之後遇到重複的函式呼叫時,就會直接查表返回答案
避免冗餘不必要的重複計算


這邊想一下,假如暴力搜索展開費式數列。
例如計算F(100),是不是比較小的那幾項都要重複計算好幾遍?




在思考建構DP演算法時,通常有一個基本框架可以遵循:



DP演算法建構框架

  1. 定義DP狀態。
    DP[i]代表原題目什麼情況下的解

  2. 推導DP狀態轉移關係式(也可稱為DP遞迴關係式)。
    DP[i]如何遞迴化簡到更小規模的問題DP[j]

  3. 釐清DP狀態的初始條件(或終止條件)。
    DP[ 初始條件 ] =?
    通常是最小規模的幾個問題 或者是 問題的最後邊界,
    而且可以紙筆計算或者人為推理出答案


如果上述三個條件都具備了,就代表DP演算法的數學形式已經確立。

接下來只要把演算法轉成對應的程式碼,就可以透過電腦進行驗證和計算答案。



實際案例與對照

如果用大家熟知的費式數列來說

通常,老師或教科書會給出如下的定義

F(n) = F(n-1) + F(n-2) , n >= 2

F(0) = 0

F(1) = 1


那麼對應到DP動態規劃的觀點,怎麼看呢?


DP狀態定義 DP[n] 就相當於F(n),費式數列的第n項。


DP狀態轉移關係式 相當於 DP[n] = DP[n-1] + DP[n-2]

費式數列的第n項 = 前兩項的和 = 費式數列的第n-1項 + 費式數列的第n-2項


DP狀態的初始條件就相當於最小規模的幾個問題 或者是 問題的最後邊界

DP[0] = 0

DP[1] = 1

定義費式數列的第零項 = 0

定義費式數列的第一項 = 1


求DP[n]也就是費式數列的第n項,
即便n很大,我們還是可以透過遞迴化簡到已知項,
最後再從已知項反推計算得到DP[n] 也就是費式數列的第n項。


這篇的目標是先讓讀者對於DP有初步的了解與認識,下一篇文章會開始用費式數列來作為整個DP特訓班系列的開頭,解說DP演算法框架的思考流程和步驟。


下一篇: DP動態規劃 深入淺出 以Fibonacci Number 費式數列 為例

求解費式數列第n項的DP程式碼

class Solution:
def fib(self, n: int) -> int:

# DP table with F(0) = 0, F(1) = 1
dp = {0: 0, 1: 1}

def getFib( i ):

if i in dp:
return dp[i]

dp[i] = getFib(i-1) + getFib(i-2)
return dp[i]
# ----------------------------------------
return getFib(n)


Reference

[1] Wiki: 動態規劃

[2] Introduction to Algorithm, CLRS

留言
avatar-img
留言分享你的想法!
就不用一直手動計算了🥹
小松鼠-avatar-img
發文者
2024/07/30
DP動態規劃 深入淺出 以Fibonacci Number 費式數列 為例提及了這篇文章,趕快過去看看吧!
👍👏👏👏👀🤗
avatar-img
小松鼠的演算法樂園
95會員
427內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
2024/09/13
給定一個整數陣列arr,和一串區間XOR請求queries。 請計算queries所請求的區間XOR值,並且以陣列的形式返回答案。
Thumbnail
2024/09/13
給定一個整數陣列arr,和一串區間XOR請求queries。 請計算queries所請求的區間XOR值,並且以陣列的形式返回答案。
Thumbnail
2024/08/27
Path with Maximum Probability 題目給定一個無向圖(雙向移動皆可), 提供每條邊的起終點,和每條邊對應的通過時的成功機率。 請問從起點start走到終點end的最高成功機率是多少? 如果完全沒有路徑可以抵達,則返回0。
Thumbnail
2024/08/27
Path with Maximum Probability 題目給定一個無向圖(雙向移動皆可), 提供每條邊的起終點,和每條邊對應的通過時的成功機率。 請問從起點start走到終點end的最高成功機率是多少? 如果完全沒有路徑可以抵達,則返回0。
Thumbnail
2024/08/21
題目敘述 664. Strange Printer 有一台奇怪的印表機, 每次操作只能連續印同樣的字母,但是列印的長度可以自由控制。 而且,印刷的時候,可以蓋過去舊的字元。 (這邊當然不合常理,讀者可以理解成塗了立可帶再蓋過去的情境) 給定一個輸入字串s,請問最少需要幾次操作,才能印出字串s?
Thumbnail
2024/08/21
題目敘述 664. Strange Printer 有一台奇怪的印表機, 每次操作只能連續印同樣的字母,但是列印的長度可以自由控制。 而且,印刷的時候,可以蓋過去舊的字元。 (這邊當然不合常理,讀者可以理解成塗了立可帶再蓋過去的情境) 給定一個輸入字串s,請問最少需要幾次操作,才能印出字串s?
Thumbnail
看更多
你可能也想看
Thumbnail
「欸!這是在哪裡買的?求連結 🥺」 誰叫你太有品味,一發就讓大家跟著剁手手? 讓你回購再回購的生活好物,是時候該介紹出場了吧! 「開箱你的美好生活」現正召喚各路好物的開箱使者 🤩
Thumbnail
「欸!這是在哪裡買的?求連結 🥺」 誰叫你太有品味,一發就讓大家跟著剁手手? 讓你回購再回購的生活好物,是時候該介紹出場了吧! 「開箱你的美好生活」現正召喚各路好物的開箱使者 🤩
Thumbnail
NVDIA黃仁勳演講有提到分散式運算,我還真的做了分散式運算的研究拿了個碩士,那分散式運算是做什麼的呢?用現在的時代用語”算力”來解釋的話,就是要處理的資料非常大量,但是單一伺服器的算力不足,所以必須聯合好幾台伺服器的算力來一起處理, 而要能夠做分散式運算的前提就是你要有一套可以操作分散式運算
Thumbnail
NVDIA黃仁勳演講有提到分散式運算,我還真的做了分散式運算的研究拿了個碩士,那分散式運算是做什麼的呢?用現在的時代用語”算力”來解釋的話,就是要處理的資料非常大量,但是單一伺服器的算力不足,所以必須聯合好幾台伺服器的算力來一起處理, 而要能夠做分散式運算的前提就是你要有一套可以操作分散式運算
Thumbnail
介紹邏輯運算的觀念,包含布林值、運算子與運算式的介紹。並說明如何使用 Python 撰寫這些觀念。
Thumbnail
介紹邏輯運算的觀念,包含布林值、運算子與運算式的介紹。並說明如何使用 Python 撰寫這些觀念。
Thumbnail
「什麼時候才能用數學歸納法?」 數學歸納法的哲學意義是,當1代入時關係成立,且n成立時發現n+1時成立,那豈不是1成立2就成立,接著3也成立,因此到∞也成立? 所有數學歸納法適用的時機是: 1. 該命題要證明的範圍在自然數系中 2. 能透過「被歸納的訊息」找到「n和n+1 or n和n-1的關係」
Thumbnail
「什麼時候才能用數學歸納法?」 數學歸納法的哲學意義是,當1代入時關係成立,且n成立時發現n+1時成立,那豈不是1成立2就成立,接著3也成立,因此到∞也成立? 所有數學歸納法適用的時機是: 1. 該命題要證明的範圍在自然數系中 2. 能透過「被歸納的訊息」找到「n和n+1 or n和n-1的關係」
Thumbnail
  程式中很常會看到千奇百怪的運算式,這些運算式都隱藏著各種運算元和運算子,這些是什麼呢?讓我們來一探究竟。   運算元是指變數、常數這類(如:A、B、C、Data、123等),運算子是指運算符號(如:+、-、*、/、%、==、<、&&等這類型),這邊就要介紹C#的運算子以及怎麼使用。
Thumbnail
  程式中很常會看到千奇百怪的運算式,這些運算式都隱藏著各種運算元和運算子,這些是什麼呢?讓我們來一探究竟。   運算元是指變數、常數這類(如:A、B、C、Data、123等),運算子是指運算符號(如:+、-、*、/、%、==、<、&&等這類型),這邊就要介紹C#的運算子以及怎麼使用。
Thumbnail
命題邏輯基本概念 在開始基礎邏輯以前我們要先了解Metalanguage(後設語言),用來討論語言的語言。我們會將命題用字母表示。如果是修過大一邏輯的哲學系朋友一定知道,我們會用大寫英文字母來代指一個命題。比方說: F:I fucked up the final exam. 這樣。 但如果是有深造過
Thumbnail
命題邏輯基本概念 在開始基礎邏輯以前我們要先了解Metalanguage(後設語言),用來討論語言的語言。我們會將命題用字母表示。如果是修過大一邏輯的哲學系朋友一定知道,我們會用大寫英文字母來代指一個命題。比方說: F:I fucked up the final exam. 這樣。 但如果是有深造過
Thumbnail
■信號的各種傅立葉變換分析 【TIPS】 DTFT是時間離散傅立葉轉換,僅僅是時間上離散化了;DTFT是對 原信號在時域離散 DFT是離散傅立葉轉換,在時域和頻域上都離散了。DFT是對DTFT在頻域上 離散,相當於對原信號在時域、頻域上都離散。 DTFT是數學家的傑作,DFT是工程師的傑作。
Thumbnail
■信號的各種傅立葉變換分析 【TIPS】 DTFT是時間離散傅立葉轉換,僅僅是時間上離散化了;DTFT是對 原信號在時域離散 DFT是離散傅立葉轉換,在時域和頻域上都離散了。DFT是對DTFT在頻域上 離散,相當於對原信號在時域、頻域上都離散。 DTFT是數學家的傑作,DFT是工程師的傑作。
Thumbnail
程式語言只是工具,更重要的是程式邏輯 【運算思維】 1.拆解: 將一個任務或問題拆解成數個步驟或部分。 2.找出規律: 預測問題的規律,並找出模式做測試。 3.歸納與抽象化: 找出最主要導致此模式的原則或因素。 4.設計演算法: 設計出能夠解決類似問題並且能夠被重複執行的指令流程。
Thumbnail
程式語言只是工具,更重要的是程式邏輯 【運算思維】 1.拆解: 將一個任務或問題拆解成數個步驟或部分。 2.找出規律: 預測問題的規律,並找出模式做測試。 3.歸納與抽象化: 找出最主要導致此模式的原則或因素。 4.設計演算法: 設計出能夠解決類似問題並且能夠被重複執行的指令流程。
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News