動態規劃演算法的核心在於拆解問題成子問題並儲存結果避免重複計算，有效降低時間複雜度。然而，實作上需注意基本情況的正確性，否則可能導致錯誤結果。除錯時，列印 DP 表格或記憶體有助於理解解法過程。選擇自頂向下或自底向上方法取決於問題特性和個人偏好，兩種方法各有其優缺點。空間最佳化技術，例如使用一維陣列取代二維陣列，能有效降低空間複雜度，尤其在多維動態規劃問題中更為重要。理解時間和空間複雜度在動態規劃中的權衡，以及如何針對特定問題進行最佳化，是提升演算法效率的關鍵。
動態規劃實作
動態規劃是一種強大的演算法技術，用於解決具有重疊子問題和最優子結構的問題。正確實作動態規劃解法需要仔細考慮基本情況、遞迴關係和空間最佳化。
正確處理基本情況
實作動態規劃解法時最常見的挑戰之一是正確處理基本情況。錯誤的基本情況可能導致錯誤或不正確的結果。總是先清楚定義和實作基本情況，然後再進行遞迴或迭代部分的解法。
例子：最長共同子序列（LCS）問題
def lcs(X, Y):
m, n = len(X), len(Y)
L = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if X[i-1] == Y[j-1]:
L[i][j] = L[i-1][j-1] + 1
else:
L[i][j] = max(L[i-1][j], L[i][j-1])
return L[m][n]
內容解密：
- 初始化DP表格：我們建立一個二維列表
L，大小為(m+1) x (n+1)，其中m和n分別是輸入字串X和Y的長度。第一行和第一列初始化為0，代表當其中一個字串為空時，最長共同子序列的長度為0。 - 填寫DP表格：我們遍歷
X和Y的每個字元。如果當前字元匹配，則L[i][j] = L[i-1][j-1] + 1，表示最長共同子序列的長度增加1。否則，我們取L[i-1][j]和L[i][j-1]的最大值，表示當前字元不匹配時的最長共同子序列。 - 傳回結果：最終結果儲存在
L[m][n]中，表示X和Y的最長共同子序列的長度。
除錯動態規劃解法
在除錯動態規劃解法時，列印DP表格或記憶化字典在不同階段是非常有幫助的。這可以幫助你瞭解解法是如何構建的，並識別遞迴關係或基本情況中的任何問題。
例子：揹包問題的DP表格列印
def knapsack(values, weights, capacity):
n = len(values)
dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(1, capacity + 1):
if weights[i-1] <= w:
dp[i][w] = max(values[i-1] + dp[i-1][w-weights[i-1]], dp[i-1][w])
else:
dp[i][w] = dp[i-1][w]
print(f"考慮物品 {i} 後的DP表格：")
for row in dp:
print(row)
print()
return dp[n][capacity]
內容解密：
- 填寫DP表格：我們根據物品的重量和價值填寫DP表格。如果當前物品的重量小於等於當前揹包容量，則我們選擇包含或不包含當前物品的最大價值。否則，我們不包含當前物品。
- 列印DP表格：每次考慮一個物品後，我們列印當前的DP表格，以觀察解法的構建過程。
- 傳回結果：最終結果是
dp[n][capacity]，表示在給定揹包容量下可以獲得的最大價值。
自頂向下與自底向上的比較
動態規劃解法可以採用自頂向下（記憶化）或自底向上（表格法）的方法。選擇通常取決於具體問題和個人偏好，但它會影響程式碼的清晰度和效能。
例子：硬幣找零問題
自頂向下（記憶化）方法
def coin_change(coins, amount, memo={}):
if amount in memo:
return memo[amount]
if amount == 0:
return 0
if amount < 0:
return float('inf')
memo[amount] = min(coin_change(coins, amount - c, memo) + 1 for c in coins)
return memo[amount]
自底向上（表格法）方法
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
內容解密：
- 自頂向下方法：這種方法遵循問題的自然遞迴結構，但可能由於函式呼叫而有更高的開銷。
- 自底向上方法：這種方法迭代地構建解法，有時對於較大的輸入更有效率。
空間最佳化技術
有時，你可以透過只跟蹤必要的先前狀態來減少空間複雜度。
例子：最長遞增子序列（LIS）問題
def longest_increasing_subsequence(nums):
if not nums:
return 0
n = len(nums)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
內容解密：
- 初始化DP陣列：我們建立一個大小為
n的陣列dp，其中dp[i]表示以nums[i]結尾的最長遞增子序列的長度。 - 填寫DP陣列：我們遍歷
nums的每個元素，並與之前的元素比較。如果nums[i] > nums[j]，則我們更新dp[i]為dp[j] + 1的最大值。 - 傳回結果：最終結果是
dp陣列中的最大值，表示最長遞增子序列的長度。
常見的動態規劃問題
動態規劃在解決複雜最佳化問題方面表現出色。三個經典例子是揹包問題、最長共同子序列（LCS）問題和矩陣鏈乘法。這些問題不僅在學術上很有趣，而且在各個領域都有實際應用。
例子：揹包問題
def knapsack(values, weights, capacity):
n = len(values)
dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(1, capacity + 1):
if weights[i-1] <= w:
dp[i][w] = max(values[i-1] + dp[i-1][w-weights[i-1]], dp[i-1][w])
else:
dp[i][w] = dp[i-1][w]
return dp[n][capacity]
內容解密：
- 初始化DP表格：我們建立一個二維表格
dp，大小為(n+1) x (capacity+1)，其中n是物品數量。 - 填寫DP表格：我們根據物品的重量和價值填寫DP表格，以確定在給定揹包容量下可以獲得的最大價值。
- 傳回結果：最終結果是
dp[n][capacity]，表示最大價值。
時間與空間複雜度在動態規劃中的重要性
動態規劃（Dynamic Programming）是一種解決複雜問題的有效方法，其核心思想是將問題分解為更小的子問題，並儲存子問題的解以避免重複計算。在動態規劃中，時間和空間複雜度是兩個非常重要的因素，它們直接影響到演算法的效率和實用性。
時間複雜度
動態規劃通常能夠顯著改善時間複雜度，尤其是對於那些具有重疊子問題和最優子結構的問題。例如，計算費波那契數列（Fibonacci Sequence）的遞迴解法具有指數時間複雜度O(2^n)，而動態規劃解法則能夠將時間複雜度降低到O(n)。
費波那契數列的動態規劃解法
def fibonacci(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
內容解密：
- 這個函式計算第n個費波那契數。
- 使用動態規劃陣列
dp儲存已經計算過的費波那契數，以避免重複計算。 - 時間複雜度為O(n)，因為只需要遍歷一次陣列。
空間複雜度
雖然動態規劃能夠改善時間複雜度，但它通常需要更多的記憶體空間來儲存子問題的解。例如，上述費波那契數列的動態規劃解法需要O(n)的空間複雜度。然而，我們可以進一步最佳化空間複雜度到O(1)。
最佳化費波那契數列計算
def fibonacci_optimized(n):
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
內容解密：
- 這個最佳化版本僅使用兩個變數
a和b來儲存前兩個費波那契數。 - 透過更新
a和b的值，避免了使用額外的陣列。 - 時間複雜度仍為O(n)，但空間複雜度降低到O(1)。
動態規劃中的時間與空間權衡
在動態規劃中，時間和空間複雜度之間通常存在權衡。例如，在解決0/1揹包問題（Knapsack Problem）時，典型的動態規劃解法使用一個二維陣列，導致O(nW)的空間複雜度，其中n是物品數量，W是揹包容量。然而，我們可以透過使用一維陣列並原地更新，將空間複雜度降低到O(W)。
最佳化0/1揹包問題解法
def knapsack_optimized(values, weights, capacity):
n = len(values)
dp = [0] * (capacity + 1)
for i in range(n):
for w in range(capacity, weights[i]-1, -1):
dp[w] = max(dp[w], values[i] + dp[w - weights[i]])
return dp[capacity]
內容解密：
- 使用一維陣列
dp來儲存不同揹包容量下的最大價值。 - 逆序遍歷揹包容量，以避免覆寫之前計算的結果。
- 時間複雜度保持不變，但空間複雜度從O(nW)降低到O(W)。
多維動態規劃中的挑戰
在多維動態規劃問題中，空間複雜度可能會隨著維度的增加而指數級增長。例如，在計算三維網格中到達某點的路徑數量時，簡單的方法是使用一個三維陣列，導致O(xyz)的空間複雜度，其中x、y和z是網格的三個維度。然而，透過觀察我們只需要前一層的資訊來計算當前層，可以進行最佳化。
三維網格路徑計數最佳化
def count_paths_3d(x, y, z):
prev = [[0] * (y + 1) for _ in range(x + 1)]
curr = [[0] * (y + 1) for _ in range(x + 1)]
# 初始化和計算邏輯
內容解密：
- 使用兩個二維陣列
prev和curr來交替儲存前一層和當前層的路徑數量。 - 這種方法將空間複雜度從O(xyz)降低到O(xy)。
動態規劃與貪婪演算法的比較分析
動態規劃（Dynamic Programming）和貪婪演算法（Greedy Algorithms）是電腦科學中兩種基本的問題解決方法。儘管兩者都旨在尋找最佳解決方案，但它們在方法和適用性上存在顯著差異。理解這些差異對於選擇適合特定問題的策略至關重要。
動態規劃的特點
動態規劃是一種透過將複雜問題分解為更簡單的子問題來解決問題的方法。當問題具有重疊子問題和最佳子結構時，動態規劃尤其有效。其核心思想是儲存子問題的結果以避免重複計算。這種方法通常比樸素的遞迴方法更高效。
動態規劃例項：揹包問題
def knapsack(values, weights, capacity):
n = len(values)
dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(1, capacity + 1):
if weights[i-1] <= w:
dp[i][w] = max(values[i-1] + dp[i-1][w-weights[i-1]], dp[i-1][w])
else:
dp[i][w] = dp[i-1][w]
return dp[n][capacity]
內容解密：
- 初始化一個二維陣列
dp，用於儲存子問題的結果。 - 遍歷每個物品和每個可能的重量，判斷是否包含當前物品以獲得最大價值。
- 如果當前物品的重量小於等於當前重量，則比較包含和不包含該物品的價值，取最大值。
- 傳回
dp[n][capacity]，即為揹包容量下的最大價值。
貪婪演算法的特點
貪婪演算法在每個步驟中做出區域性最優選擇，希望能夠得到全域性最優解。它們通常比動態規劃解決方案更簡單、更直觀。貪婪演算法適用於區域性最優選擇能夠導致全域性最優解的問題。
貪婪演算法例項：揹包問題（非最優）
def greedy_knapsack(values, weights, capacity):
items = sorted(zip(values, weights), key=lambda x: x[0]/x[1], reverse=True)
total_value = 0
for value, weight in items:
if capacity >= weight:
capacity -= weight
total_value += value
else:
break
return total_value
內容解密：
- 根據物品的價值與重量比進行排序，優先選擇比值高的物品。
- 遍歷排序後的物品列表，將能夠裝入揹包的物品累加到總價值中。
- 如果揹包容量不足，則停止並傳回總價值。
動態規劃與貪婪演算法的比較
| 特點 | 動態規劃 | 貪婪演算法 |
|---|---|---|
| 問題分解 | 將問題分解為重疊子問題 | 在每個步驟做出區域性最優選擇 |
| 適用問題 | 具有重疊子問題和最佳子結構的問題 | 區域性最優選擇能夠導致全域性最優解的問題 |
| 計算效率 | 通常較高，避免重複計算 | 通常較高，但可能不是最優解 |
何時使用動態規劃或貪婪演算法？
使用動態規劃當：
- 問題可以分解為更小的、重疊的子問題。
- 問題的最佳解取決於子問題的最佳解。
- 需要在多個可能的解中找出最佳解。
使用貪婪演算法當：
- 問題可以透過在每個步驟做出區域性最優選擇來解決。
- 區域性最優選擇能夠導致全域性最優解。
- 不需要考慮所有可能的解。