舉個栗子

有 \(N\) 階的樓梯，從第 \(1\) 階開始，每次可以走 \(1\) 階或走 \(2\) 階，請問剛好走到第 \(N\) 階有多少種方法？

舉個栗子

有 \(N\) 階的樓梯，從第 \(0\) 階開始，每次可以走 \(1\) 階或走 \(2\) 階，請問剛好走到第 \(N\) 階有多少種方法？

• 定義 \(dp[i]\) 為剛好走到第 \(i\) 階的方法數
• \(dp[0] = 1, dp[1] = 1\)
• \(dp[i] = dp[i-1] + dp[i-2] \quad \forall i \geq 2\)
• 答案就是 \(dp[N]\)

• \(dp[i]\)：狀態
• \(dp[0] = 1, dp[1] = 1\)：初始狀態
• \(dp[i] = dp[i-1] + dp[i-2]\)：狀態轉移式

DP 的性質

1. 重複子問題：同一個狀態可能會被用到很多次

\(f(2)\) 被呼叫兩次，算過一次就紀錄起來，之後可以直接查，不需要重算

DP 問題的本質是分治與遞迴，而 DP 的精髓在於算過的答案不要重算

• 紀錄子問題 (Memoization)

2. 最佳子結構：大問題的答案可以從小問題的答案推出

「\(f(4)\) 可以從 \(f(3)\) 跟 \(f(2)\) 推得」

3. 無後效性：每個狀態的轉移來源不能相互依賴

「要算 \(f(a)\) 需要先算出 \(f(b)\)，但要算 \(f(b)\) 需要先算出 \(f(a)\) …？」

3. 無後效性：每個狀態的轉移來源不能相互依賴

把每個狀態想像成節點，轉移關係想像成邊

則合理的狀態定義必定會使所有狀態形成一個 DAG

而可行的轉移順序便是該圖的其中一種拓樸排序

DP 的步驟

1. 觀察問題，定義好狀態
   • 可以先不管複雜度，但要考慮好所有情況
   • 題目列出的條件都可能可以拿來當狀態的參數
2. 推出轉移式
   • 好好考慮該如何切成小問題
   • 切出來的小問題必須包含所有可能情況，同時又必須互相獨立
   • 發現很難轉移 \(\Rightarrow\) 修改狀態定義
3. 找到一個合理的轉移順序
   • 費式數列：從 \(f(0)\) 推到 \(f(N)\)
   • 區間 DP：從小區間推到大區間
   • 位元 DP：從小集合推到大集合（或是從 \(0\) 到 \(2^N\)）
4. 優化狀態／轉移過程

實作方式

• Top down

int f[100];
int F(int x) {
	if (x <= 1) return f[x] = 1;
	return f[x] = F(x-1) + F(x-2);
}

• Bottom up

int f[100];
f[0] = f[1] = 1;
for (int i = 2; i < 100; i++) {
	f[i] = f[i-1] + f[i-2];
}

• Top down
  • 使用時機
    • 有用到的狀態很稀疏時
    • 轉移確定無後效性，但合理的轉移順序很難找時
  • 旅行推銷員問題
• Bottom up
  • 優點：狀態稠密時，常數較小
  • 優點：好套優化
    • 常見 DP 優化都是把要考慮的轉移來源開個資結處理（前綴和陣列／線段樹／BIT／李超線段樹），或是利用狀態的單調性二分搜、均攤優化（單調隊列／四邊形優化）

Bottom up 又可以分兩種

• pull：把答案從子問題「拉上來」

  ​f[i] = f[i-1] + f[i-2];
  

• push：把子問題答案主動「推」到大問題

  ​f[i+2] += f[i];
  ​f[i+1] += f[i];
  

視實作方便度決定，大部分都是用 pull，少數題目用 push 比較好寫例如這題（KMP+DP）

2018北市賽 幸運表格
\(n \times m\) 的地圖，每格上面有權重
求從某個格子開始往右／往下移動直到超出邊界，經過的格子權重和最大是多少？

如果題目是從左上角走到右下角的答案

• \(dp[i][j] =\) 走到 \((i, j)\) 的最大權重和
• \(dp[i][j] = max(\)從上面走來\(,\) 從左邊走來\()\)
• \(dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + w[i][j]\)
• 答案 \(dp[n][m]\)

考慮原題的移動方式，修改一下轉移

• \(dp[i][j] = max(\)從上面走來\(,\) 從左邊走來\(,\) 從這格開始\()\)
• \(dp[i][j] = max(dp[i-1][j], dp[i][j-1], 0) + w[i][j]\)
• 答案 \(max(dp[n][1\sim m], dp[1\sim n][m])\)

經典到不能再經典

• 長度 \(N\) 的序列 \(a\)，輸出 \(a\) 當中最長非嚴格遞增子序列的
  1. 長度
  2. 個數
  3. 最小字典序的 LIS
  • subtask 1: \(N \leq 5000\)
  • subtask 2: \(N \leq 10^5\)

.

P.S. 行尾不要輸出多餘空白

先求長度

• \(dp[i] \equiv\) 結尾位置為 \(i\) 的 LIS 長度。
• \(dp[i] = max_{j < i \land a[j] \leq a[i]} \{ dp[j] \} + 1\)
• 答案是：\(max_{1 \leq i \leq N} \{ dp[i] \}\)

轉移直接用迴圈的話複雜度 \(O(N^2)\)

\(O(N \log N)\) 作法一

設 \(t[len]\) 為所有 \(dp[i] = len\) 中最小的 \(A[i]\)

• 有了 \(t\) 要怎麼算 \(dp[i]\)？

• 有了 \(t\) 要怎麼算 \(dp[i]\)？
• 從所有 \(\leq A[i]\) 的 \(t[len]\) 中，找出最大的 \(len\)。
• \(dp[i] = maxlen + 1\)

• 有了 \(t\) 要怎麼算 \(dp[i]\)？
• 從所有 \(\leq A[i]\) 的 \(t[len]\) 中，找出最大的 \(len\)。
• \(dp[i] = maxlen + 1\)
• 如果所有 \(t[len]\) 都 \(> A[i]\)，那就代表前面不能接任何數字
• \(\Rightarrow\) \(dp[i] = 1\)

Claim：\(t[len]\) 會單調遞增
Proof：反證法

• 設存在 \(j < i\) 使得 \(t[j] > t[i]\)
• 觀察下圖，會發現 \(t[j]\) 不滿足定義 \(\Rightarrow\) 矛盾

Claim：\(t[len]\) 會單調遞增
找 \(maxlen\)？

Claim：\(t[len]\) 會單調遞增
找 \(maxlen\)？

二分搜！

\(O(N \log N)\) 作法二

觀察轉移式：\(dp[i] = max_{j < i \land a[j] \leq a[i]} \{ dp[j] \} + 1\)
也就是說，可能的轉移點 \(j\) 滿足：

1. \(j < i\)
2. \(A[j] \leq A[i]\)

所有的 \(j\) 當中最大的 \(dp[j]\) 就是轉移點。

可以用一個區間查詢的資料結構維護區間 \(dp\) 值最大值。
查詢 \(dp[i]\) 的最佳轉移點可以用 \(query(1, i-1)\) 解決。

可以用一個區間查詢的資料結構維護區間 \(dp\) 值最大值。
查詢 \(dp[i]\) 的最佳轉移點可以用 \(query(1, i-1)\) 解決。

但還有一個條件：\(A[j] \leq A[i]\)？

可以用一個區間查詢的資料結構維護區間 \(dp\) 值最大值。
查詢 \(dp[i]\) 的最佳轉移點可以用 \(query(1, i-1)\) 解決。

但還有一個條件：\(A[j] \leq A[i]\)？

DP 順序：從 \(A[i]\) 越小的開始做！

可以用一個區間查詢的資料結構維護區間 \(dp\) 值最大值。
查詢 \(dp[i]\) 的最佳轉移點可以用 \(query(1, i-1)\) 解決。

但還有一個條件：\(A[j] \leq A[i]\)？

DP 順序：從 \(A[i]\) 越小的開始做！

這樣可以保證 \(query(1, i-1)\) 得到的答案必定滿足 \(A[j] \leq A[i]\)

資結可以使用線段樹
但其實這題條件很特別，可以用 BIT

• 詢問區間只有前綴
• 單點修改時只會把 \(0\) 改成 \(dp[i]\)（數字只會改大不會改小）

求 LIS 個數？

求 LIS 個數？
\(cnt[i]\) 表示以 \(i\) 結尾的最長遞增子序列數量

假設已經算出 \(dp[i]\)，考慮求 \(cnt[i]\)
則 \(cnt[i] = \sum cnt[j]\)，\(j\) 滿足：

1. \(j < i\)
2. \(A[j] \leq A[i]\)
3. \(dp[j] = dp[i] - 1\)

• 使用作法二，維護最大值的同時也維護滿足該最大值的數量
• 詢問的時候除了回傳最大值也一併回傳滿足該最大值的數量
• 如何維護交給大家練習

求最小字典序 LIS？

• 求最小字典序的作法
  • Greedy 地由前面往後掃
  • 能先拿就拿
• DP 回溯解的方向
  • 由後往前回推

兩個方向不同，怎麼辦？

• 求最小字典序的作法
  • Greedy 地由前面往後掃
  • 能先拿就拿
• DP 回溯解的方向
  • 由後往前回推

兩個方向不同，怎麼辦？

把原本的序列倒過來做 DP！

• 求最小字典序的作法
  • Greedy 地由後面往前掃
  • 能先拿就拿
• DP 回溯解的方向
  • 由後往前回推

把原本的序列倒過來做 DP！

原本求 LIS 改成求 LDS（最長遞減子序列）

練習

• 裸題
• NEOJ 421
• TOI 初選 pC

背包問題的變形：

• 0/1 背包（最原始的）
• 無限背包
• 有限背包

0/1 背包 I — 狀態的維度【考慮第 \(i\) 個，總重量】

\(N\) 個物品有各自的重量 \(w_i\) 和價值 \(v_i\)
背包重量上限 \(W\)，求最大價值？

• \(N \leq 100\)
• \(W \leq 10^5\)
• \(v_i \leq 10^9\)

• \(dp[i][w]\) 考慮到第 \(i\) 個物品，且此時背包已經裝了總重 \(w\) 的物品的最大總價值

• \(dp[i][w]\) 考慮到第 \(i\) 個物品，且此時背包已經裝了總重 \(w\) 的物品的最大總價值
• \(dp[i][w] = max(\)拿\(i,\) 不拿\(i)\)
• \(dp[i][w] = max(dp[i-1][w-w_i] + v_i, dp[i-1][w])\)

• \(dp[i][w]\) 考慮到第 \(i\) 個物品，且此時背包已經裝了總重 \(w\) 的物品的最大總價值
• \(dp[i][w] = max(\)拿\(i,\) 不拿\(i)\)
• \(dp[i][w] = max(dp[i-1][w-w_i] + v_i, dp[i-1][w])\)
• 答案會是 \(max_{0 \leq w \leq W} \{dp[N][w]\}\)

• \(dp[i][w]\) 考慮到第 \(i\) 個物品，且此時背包已經裝了總重 \(w\) 的物品的最大總價值
• \(dp[i][w] = max(\)拿\(i,\) 不拿\(i)\)
• \(dp[i][w] = max(dp[i-1][w-w_i] + v_i, dp[i-1][w])\)
• 答案會是 \(max_{0 \leq w \leq W} \{dp[N][w]\}\)
• 初始狀態和實作細節交給大家練習
• \(dp\) 表格大小開 \(N \times W\)
• 寬只到 \(W\) 是因為超過 \(W\) 根本不是合法狀態
  時間跟空間複雜度 \(O(NW)\)

空間 \(O(NW)\) 好像太緊了

觀察到每個狀態 \(dp[i][w]\) 的轉移來源都只在上一列

除此之外其他狀態根本用不到

滾動陣列 I

• 開兩個陣列 \(dp0, dp1\) 交替使用
• 假設現在在 \(dp1\)，那麼就從 \(dp0\) 轉移
• 假設現在在 \(dp0\)，那麼就從 \(dp1\) 轉移

空間複雜度 \(O(W)\)

好還要更好！
兩個陣列 \(\Rightarrow\) 一個陣列

滾動陣列 II

• 只開一個陣列 \(dp\)
• 新的狀態要覆蓋舊的狀態
• 確保每個新的狀態的轉移來源都不能被覆蓋到

滾動陣列 II

• 只開一個陣列 \(dp\)
• 新的狀態要覆蓋舊的狀態
• 確保每個新的狀態的轉移來源都不能被覆蓋到
• DP 順序：從 \(dp[W]\) 倒著做到 \(dp[0]\)

0/1 背包 II — 狀態的維度【考慮第 \(i\) 個，總價值】

\(N\) 個物品有各自的重量 \(w_i\) 和價值 \(v_i\)
背包重量上限 \(W\)，求最大價值？

• \(N \leq 100\)
• \(W \leq 10^9\)
• \(v_i \leq 10^3\)

• \(dp[i][v]\) 考慮到第 \(i\) 個物品，且此時背包已經裝了總價值 \(v\) 的物品的最小總重

• \(dp[i][v]\) 考慮到第 \(i\) 個物品，且此時背包已經裝了總價值 \(v\) 的物品最小總重
• \(dp[i][v] = min(\)拿\(i,\) 不拿\(i)\)
• \(dp[i][v] = min(dp[i-1][v-v_i] + w_i, dp[i-1][v])\)

• \(dp[i][v]\) 考慮到第 \(i\) 個物品，且此時背包已經裝了總價值 \(v\) 的物品最小總重
• \(dp[i][v] = min(\)拿\(i,\) 不拿\(i)\)
• \(dp[i][v] = min(dp[i-1][v-v_i] + w_i, dp[i-1][v])\)
• 假設所有東西總價值和 \(sv = \sum_{i=1}^{N} v_i\)。
• 取答案的方法：
  • 從 \(dp[N][sv]\) 開始倒著掃到 \(dp[N][0]\)
  • 只要掃到某個 \(v\) 滿足 \(dp[N][v] \leq W\)，\(v\) 就是答案

• \(dp[i][v]\) 考慮到第 \(i\) 個物品，且此時背包已經裝了總價值 \(v\) 的物品最小總重
• \(dp[i][v] = min(\)拿\(i,\) 不拿\(i)\)
• \(dp[i][v] = min(dp[i-1][v-v_i] + w_i, dp[i-1][v])\)
• 假設所有東西總價值和 \(sv = \sum_{i=1}^{N} v_i\)。
• 取答案的方法：
  • 從 \(dp[N][sv]\) 開始倒著掃到 \(dp[N][0]\)
  • 只要掃到某個 \(v\) 滿足 \(dp[N][v] \leq W\)，\(v\) 就是答案
• \(dp\) 表格大小開 \(N \times sv\)
  時間複雜度 \(O(N \sum_{i=1}^{N} v_i)\)

無限背包

\(N\) 個物品有各自的重量 \(w_i\) 和價值 \(v_i\)，且數量都有無限多個
背包重量上限 \(W\)，求最大價值？

• \(N \leq 100\)
• \(W \leq 10^5\)
• \(v_i \leq 10^9\)

• \(dp[i][w]\) 考慮到第 \(i\) 個物品，且此時背包已經裝了總重 \(w\) 的物品的最大總價值
• \(dp[i][w] = max(dp[i][w-w_i] + v_i, dp[i-1][w])\)

要多少有多少，所以拿了一個 \(i\) 之後不必回到 \(i-1\) 的狀態

有限背包

• \(dp[i][w]\) 考慮到第 \(i\) 個物品，且此時背包已經裝了總重 \(w\) 的物品的最大總價值
• \(dp[i][w] = max(\)拿\(0\)個\(i,\)拿\(1\)個\(i,\)拿\(2\)個\(i, ...,\)拿\(c_i\)個\(i)\)
• \(dp[i][w] = max(\\dp[i-1][w],\\dp[i-1][w-w_i] + v_i,\\dp[i-1][w-2w_i] + 2v_i,\\...\\dp[i-1][w-c_i \cdot w_i] + c_i \cdot w_i)\)

複雜度 \(O(NW\cdot max(c_i))\)

• 把第 \(i\) 個物品看成 \(c_i\) 個獨立的物品
• 直接一起做 0/1 背包

• 把第 \(i\) 個物品看成 \(c_i\) 個獨立的物品
• \(N\) 個物品都這樣做，直接一起做 0/1 背包
  複雜度 \(O(NW\cdot max(c_i))\) 還是沒變

優化

• 把第 \(i\) 個物品拆成 \(1\) 個 \(i\)，\(2\) 個 \(i\)，\(4\) 個 \(i\)，…
• 一直用 \(2\) 的冪次拆直到不夠拆，餘下的 \(i\) 綁在一起。
• \(N\) 個物品都這樣拆，把它們一起做 0/1 背包

優化

• 把第 \(i\) 個物品拆成 \(1\) 個 \(i\)，\(2\) 個 \(i\)，\(4\) 個 \(i\)，…
• 一直用 \(2\) 的冪次拆直到不夠拆，餘下的 \(i\) 綁在一起。
• \(N\) 個物品都這樣拆，把它們一起做 0/1 背包
  複雜度 \(O(NW\cdot \log(max(c_i)))\)

優化

• 把第 \(i\) 個物品拆成 \(1\) 個 \(i\)，\(2\) 個 \(i\)，\(4\) 個 \(i\)，…
• 一直用 \(2\) 的冪次拆直到不夠拆，餘下的 \(i\) 綁在一起。
• \(N\) 個物品都這樣拆，把它們一起做 0/1 背包
  複雜度 \(O(NW\cdot \log(max(c_i)))\)

拆的方法只要保證能湊出 \([0, c_i]\) 之間任意數量的物品
接下來 DP 就會自動幫你算出最好的答案

• 有限背包因為轉移點有時限（\(\because\) 物品數量有限）
• 所以可以套單調隊列優化
• 這裡不細講，忘記的可以回去看 DP II 的簡報

練習

• 2021 附中校隊培訓模競 pE
• NEOJ 159