DP 複習與練習 I

Gino

第一次講課是不是要自我介紹啊

題單在此

課前提醒

這堂課的定位是複習

主要會再講解一次 DP 的性質還有複習一些重要的經典題

難度約中偏易，然後我可能會飆車

如果上到一半發現有不懂的地方可以在 Discord 的閒聊專區或問題討論區發問

或是回去翻 DP I 跟 DP II 的簡報

再讓我囉嗦一下

然後因為臨時調課

這堂課的簡報是今天爆肝生出來的

內容可能不是很多還請見諒（#每日關心Foxyy的簡報進度）

預計一個小時就會講完，剩下兩個小時讓大家刷題 + 提問 + 在 dc 哈拉

很放鬆的一堂課 OwO

再讓我囉嗦一下下下下下

DP 練習還有一堂課

下次上課會從題單裡面挑一些有趣的題目（我勉強會寫的）來講解

然後如果三生有幸我能夠學會那些 DP 優化的話也會講解

四邊形優化好難qwq

目錄

  • 什麼是 DP
  • DP 經典題
    • 暖身：二維路徑 DP
    • LIS
      • 二分搜優化
      • 資結優化
      • 求 LIS 數量
      • 求最小字典序 LIS
    • 背包問題
      • 0/1 背包
      • 滾動陣列
      • 無限背包
      • 有限背包
  • 練習時間

DP 是啥

舉個栗子

有 \(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)
  1. 最佳子結構：大問題的答案可以從小問題的答案推出

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

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

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

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

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

則合理的狀態定義必定會使所有狀態形成一個 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）

經典題目 I — 二維路徑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])\)

經典題目 II — LIS

經典到不能再經典

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

.

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]\)

\(A[i]\) 4 2 6 5 1 7 3 9
\(dp[i]\) 1 1 2 2 1 3 2 4
\(len\) 1 2 3 4
\(t[len]\) 1 3 7 9
  • 有了 \(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\) 結尾的最長遞增子序列數量

\(A[i]\) 4 2 6 5 1 7 3 9
\(dp[i]\) 1 1 2 2 1 3 2 4
\(cnt[i]\) 1 1 2 2 1 4 2 4

假設已經算出 \(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（最長遞減子序列）

練習

經典題目 III — 背包問題

背包問題的變形：

  • 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 的簡報

練習

提問時間與練習時間 :D

有人想唱歌或分享酷酷的科技可以開麥 OvO

或是看 @Foxyy 直播製作下禮拜的簡報

Select a repo