動態規劃基礎

5.1 動態規劃的定義。

動態規劃 (Dynamic Programming, DP) ——是一種優化方法，用於通過將其拆分為更簡單的子問題來解決複雜問題。動態規劃 對於可以分解為重疊子問題和具有最佳子結構的問題非常有效。

工作原則：

1. 最佳子結構：

如果問題的最佳解決方案可以從其子問題的最佳解決方案構建，那麼該問題具有最佳子結構。 這意味著可以通過解決幾個小的子問題來解決大問題。

2. 重疊子問題：

如果問題的子問題在解決過程中多次重複，則該問題具有重疊子問題。動態規劃 通過記住已解決子問題的結果（備忘錄）來有效解決具有重疊子問題的問題。

3. 備忘錄和表格法：

備忘錄（自上而下）：一種遞歸方法，即子問題的結果 被保存在記憶中以避免重複計算。

表格法（自下而上）：一種迭代方法，即子問題的結果 被計算並保存在表中（通常為數組），以用於 計算最終結果。

利用動態規劃方法解決的問題示例

5.2 背包問題。

問題:

有一組物品，每個物品都有重量和價值。需要選擇物品 將其放入具有有限承載能力的背包中，以最大化總價值。

重要！ 與容易用貪婪算法解決的類似問題不同， 在此問題中無法對物品進行分割。

解決方案:

創建一個表格，其中的行代表物品，而列代表背包的可能容量。 單元格中的值表示對應數量物品和容量的最大價值。

時間複雜度: O(n * W)，其中n為物品數量，W為背包容量。

Python代碼示例：

def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
            
    for i in range(1, n + 1):
        for w in range(W + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]
            
    return dp[n][W]
        
        

5.3 最短路徑問題

問題:

在加權圖中找到所有頂點對之間的最短路徑。

解決方案:

使用一個表格，其中行和列對應於圖的頂點。 單元格中的值表示兩個頂點之間的最短距離。

時間複雜度: O(V^3)，其中V為頂點數量

Python代碼示例：

def floyd_warshall(graph):
    v = len(graph)
    dist = list(map(lambda i: list(map(lambda j: j, i)), graph))
            
    for k in range(v):
        for i in range(v):
            for j in range(v):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
            
    return dist
        
        

5.4 動態規劃與其他方法的比較。

與暴力方法 (brute force) 的比較：

時間複雜度：

• 暴力方法：通常具有指數時間複雜度（例如， Fibonacci問題的O(2^n)）。
• 動態規劃：將時間複雜度減少到多項式（例如，Fibonacci問題的O(n)）。

空間複雜度：

• 暴力方法：可能使用較少的內存，但時間成本高。
• 動態規劃：可能使用更多的內存來存儲中間結果（例如，Fibonacci問題 使用備忘錄的O(n)），但具有時間優勢。

與貪婪算法 (greedy algorithms) 的比較：

最佳性：

• 貪婪算法：不一定找到全局最優解決方案，但 運行速度更快，實現更簡單。
• 動態規劃：找到全局最優解決方案，但 需要更多的計算資源。

問題示例：

• 貪婪算法：分數背包問題 (fractional knapsack), 最小生成樹 (MST)。
• 動態規劃：整數背包問題， 最長公共子序列 (LCS)。