究竟什麼是 動態規劃DP?

ameenfahmy null on Unsplash

動態規劃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