Dynamic Programming

動態規劃在尋找有很多重疊子問題的情況的最佳解時有效。

動態規劃儲存遞迴時計算子問題的結果，
因而不會在解決同樣的問題時花費時間。

適用條件

最佳子結構 Optimal Substructure

如果問題的最佳解所包含的子問題的解也是最佳的，我們就稱該問題具有最佳子結構性質（即滿足最佳化原理）。最佳子結構性質為動態規劃演算法解決問題提供了重要線索。

無後效性 Without Aftereffect

即子問題的解一旦確定，就不再改變，不受在這之後、包含它的更大的問題的求解決策影響。

重疊子問題 Overlapping Subproblems

子問題重疊性質是指在用遞迴演算法自頂向下對問題進行求解時，每次產生的子問題並不總是新問題，有些子問題會被重複計算多次。動態規劃演算法正是利用了這種子問題的重疊性質，對每一個子問題只計算一次，然後將其計算結果儲存在一個表格中，當再次需要計算已經計算過的子問題時，只是在表格中簡單地檢視一下結果，從而獲得較高的效率，降低了時間複雜度。

狀態轉移方程 State-Transition Equation

定義

狀態 State

描述子問題之性質

階段 Stage

一些性質相近，可以同時處理的狀態集合

決策 Decision

每個階段中做出的一些選擇性的行動

如何用動態規劃解決問題

1. 是否適用動態規劃

通常是一個找尋 極值/最佳解 的問題

2. 決定狀態

  1. 此問題的最簡單狀態（Base Cases）
  2. 此問題會有什麼狀態

3. 描述狀態之間的遞迴關係（A Recurrence Relation to Transition Between States）

做了什麼決策，讓狀態改變，到達[前/後]一個狀態

a. 先完成 Top-Down DP
b. Top-Down → Bottom-UP

參考 Leetcode # 1770. Maximum Score from Performing Multiplication Operations

 

多對一 → 一對多

參考 Leetcode # 1335. Minimum Difficulty of a Job Schedule

c. Optimize Space Complexity

注意事項

考慮邏輯是否合理

考慮 time/space complexity 是否過大

題型分類

多選一

從前 n 個選一個

Leet Code #746. Min Cost Climbing Stairs

此題也可採取 Top-Down DP (Recursion + Memoization)

 

# Bottom-Up DP
class Solution:
  def minCostClimbingStairs(self, cost: List[int]) -> int:
    min_cost = [0] * (len(cost) + 1)
    for i in range(2, len(cost) + 1):
      min_cost[i] = min(min_cost[i - 1] + cost[i - 1], min_cost[i - 2] + cost[i - 2])

    return min_cost[-1]

 

Optimized Space Complexity: O(len(cost))O(1)

class Solution:
  def minCostClimbingStairs(self, cost: List[int]) -> int:
    # min_cost(n) = min(min_cost(n - 1) + cost[n - 1], min_cost(n - 2) + cost[n - 2])
    min_cost = [0, 0]
    for i in range(2, len(cost) + 1):
      min_cost = [min_cost[1], min(min_cost[1] + cost[i - 1], min_cost[0] + cost[i - 2])]
    return min_cost[1]
Leet Code #55. Jump Game

 

class Solution:
  def canJump(self, nums: List[int]) -> bool:
    memo = [False for i in range(len(nums))]
    memo[-1] = True
    
    for i in range(len(nums) - 2, -1, -1):
      furthestJump = min(i + nums[i], len(nums) - 1)
      for j in range(i + 1, furthestJump + 1):
        if memo[j] == True:
          memo[i] = True
          break
          
    return memo[0]

[選/不選]前一個

Leet Code #198. House Robber

其實這題可說是 #746. Min Cost Climbing Stairs 的變形
如果自左搶劫至右（搶劫順序與最大收益無關）

\begin{align*}
DP[i] :&= 至第 i 間屋子為止的最大收益 \\
& = \max(搶這間, 不搶這間) = \max(nums[i] + DP[i – 2], DP[i – 1])
\end{align*}

又 DP[i] 只會在計算 DP[i + 1] 和 DP[i + 2] 時被參照
因此我們可以將 space complexity 抑制至 O(1)

 

class Solution:
  def rob(self, nums: List[int]) -> int:
    DP = [0, nums[0]] # Do not rob first house or rob

    for i in range(1, len(nums)):
      cur = max(nums[i] + DP[0], DP[1]) # Maximum profit at i-th house
                                        #   := Rob i-th house or not 

      DP[0] = DP[1] # Maximum profit at (i - 1)-th house
      DP[1] = cur.  # Maximum profit at i-th house

    return DP[1]

※ 本題相關例題：

Multidimensional DP

dp[stage][…]

dp[k + 1][l:r + 1] chosen from e[l] + dp[k][l + 1:r + 1],  dp[k][l:r] + e[r + 1]
dp[k + 1][l:r + 1] chosen from [dp[k][l:i]+dp[k][i + 1:r + 1] for i in range(l, r)]
dp[k + 1][s] chosen from [dp[k][s] + e[k + 1][s] for s in situations]

Leetcode # 2361. Minimum Costs Using the Train Line

dp[i][j]

Top-Down (Recursive)

從母問題開始，利用遞迴拆解為子問題

Memoization

Cache the results of function calls
and return the cached result
if the function is called again with the same inputs.

將已計算的結果儲存起來，省去再次計算的時間

Template

global dp
dp = {}
# ...
def fn(...):
  if ... not in dp:
    # ...
    dp[...] = # ...
  return dp[...]

Python: @lru_cache

Bottom-Up (Iterative)

從最基本的子問題開始，利用已解答的子問題向上逐步解開母問題

Tabulation

Store the results of the subproblems in a table
and use these results to solve larger subproblems until we solve the entire problem.

Optimize Space Complexity

和 top-down 的 memoization 不同
bottom-top 時，你可以自行決定 table的生成順序
而得以捨去已經使用完畢的 table 以減少記憶體用量

Rolling DP

假設 table 名為 dp
有些時候，在計算 dp[k] (k = 0, 1, .., K + 1) 時
你只需要用到 dp[k – 1] 的資料
這時你也可以改成只使用
prev_dp (previous dp) = dp[k – 1]
和 curr_dp (current dp) = dp[k] 去儲存 table
這會使得你的 space complexity 從 O(K * f(x)) 變為 O(f(x))

 

示例
 
Template
prev_dp = # ...
for k in range(1, height):
  curr_dp = # ...
  for i in range(1, width): 
    curr_dp[i] = #...
  prev_dp = curr_dp
len(dp[k + 1]) == len(dp[k]) – 1

 

Template

dp[k + 1][i] 可能會用到：dp[k][i],  dp[k][i+1, …, i + l – 1],  dp[k][i + l]

for k in range(1, height):
  for i in range(1, width[k - 1] - l): 
    # ...
其他與 dp (DP-Table) 生成順序有關的題目

Top-Down 和 Bottom-UP的比較

  • top-down 的編寫比較直觀
  • bottom-uP 比較有效率
    • 少了 recursion 的 call stack 成本 
    • space complexity 可能被 optimized 

Time/Space Complexity

In many cases, the space complexity is the number of states, and the time complexity is the number of states multiplied by the cost of calculating a state.

與其他演算法的差異

Top-Down DP vs. Backtracking 回溯法

The difference between backtracking and top-down dp.

DP vs. Greedy Algorithm

greedy algorithm 有 optimal substructure
但沒有 overlapping subproblems

DP vs. Divide and Conquer

divide and conquer 也將母問題拆解成子問題
但沒有 overlapping subproblems

經典例題

Leet Code #509. Fibonacci Number

\begin{align*}
& f_0 = 0,\enspace f_1 = 1 \\
& f_n = f_{n – 1} + f_{n – 2},\enspace \forall \enspace n > 1
\end{align*}

使用 recursive function 的話，
計算F(n)時會計算兩次F(n – 2)（因為在計算F(n – 1)時也會再計算一次F(n – 2)）

使用動態規劃手法將不再計算已計算過的斐波那契數

 

class Solution:
  def __init__(self):
    self.fibonacci_seq = [0, 1]
  def fib(self, n: int) -> int:
    if n >= len(self.fibonacci_seq):
      self.fibonacci_seq.append(self.fib(n - 1) + self.fib(n - 2))
    return self.fibonacci_seq[n]

※ 本題相關例題：

Kadane’s Algorithm (Maximum Sum Subarray Problem)

用以解決 Maximum Sum Subarray Problem

關鍵在於使用兩個變數來記錄最大值：

  • max_ending_here：現在仍持續著的最長序列之長度
  • max_so_far：到目前為止發現過的最長序列之長度

這個方法的關鍵點是當條件不符所分割出來的所有子序列不會互相重疊

請參考：Leetcode # 53. Maximum Subarray (Kadane’s Algorithm)

其他DP例題

Ref

  1. WIKIPEDIA
  2. GfG
  3. TIOJ

Last Updated on 2023/08/18 by A1go

目錄

→ 目錄
Bitnami