套路一：基本 1 型（時間序列）

觀念：

  • 給一 sequence, 每個元素可以被視為一天, 且「今天」的狀態只取決於「昨天」的狀態

套路：

  • 定義 dp[i][j] 代表第 i 輪的第 j 個狀態
  • 想辦法將 dp[i][j] 與前一輪的狀態 dp[i - 1][j] 產生關聯
  • 最終的結果是 dp[last][j] 中的某種 aggregation（min, max, sum…）

例題：

套路二：基本 2 型（加強版時間序列）

觀念：

  • 給一 sequence, 每個元素可以被視為一天, 且「今天」的狀態取決於之前「某一天」的狀態, 需要進行挑選

套路：

  • dp[i] 表示第 i 輪的狀態, 通常這個狀態必須與元素 i 直接有關
  • 想辦法將 dp[i] 與之前的狀態 dp[j] 產生關聯, 其中 1 ≤ j < i
  • 最終的結果是 dp[i] 中的其中一個

例題：

套路三：雙序列型

觀念：

  • 給兩個 sequence s、t, 讓你對它們搞事情

套路：

  • dp[i][j] 代表 s[1:i]、t[1:j] 的 subproblem 求解
  • 將 dp[i][j] 跟之前的狀態 dp[i - 1][j]、dp[i][j - 1]、dp[i - 1][j - 1] 去做轉移
  • 最終的結果是 dp[m][n]

例題：

套路四：區間 1 型

觀念：

  • 給一 sequence s, 明確要求分割成 k 個區間, 要你計算這些區間某個最優性質

套路：

  • dp[i][k] 代表 s[1:i] 分割成 k 個區間時所能得到的最優解
  • 搜尋最後一個區間的起始位置 j, 將 dp[i][k] 分割成 dp[j - 1][k - 1] 和 s[j:i]
  • 最終的結果是 dp[n][k]

例題序列型：

套路五：區間 2 型

觀念：

  • 給一 sequence s, 求針對該 sequence 的最優解

套路：

  • dp[i][j] 代表 s[i:j] 的 subproblem 求解
  • 將大區間 dp[i][j] 往小區間 dp[i'][j'] 轉移
    • for loop 外層循環是區間大小
    • for loop 內層循環是起始位置
  • 最終的結果是 dp[1][n]

例題：

套路六：背包型

觀念：

  • 給 n 件物品, 每個物品可用、可不用（或者有若干個不同的用法）, 要求以某個有上限 c 的代價來實現最大收益
  • 有時候會反過來，要求以某個有下限的收益來實現最小代價

套路：

  • dp[i][c] 代表考慮只從前 i 件物品的 subset 中選擇、代價為 c 的最大收益
    其中 c = 1, 2, ..., C（逐個列舉）
  • 將 dp[i][c] 往 dp[i - 1][c'] 轉移, 也就是考慮如何使用物品 i, 對代價／收益的影響
    • 外層循環是物品編號 i
    • 內層循環是遍歷「代價」所有可能的值
  • 最終的結果是 max{dp[n][c]}, for c = 1, 2, ..., C

例題：