動態規劃專題課程

Introduction to Dynamic Programming

2023 社群⽉演算法專題課程
2023 CISCON Algorithm Course
陳俊安 Colten
⾃我介紹 - 陳俊安 Colten
● 國⽴成功⼤學資訊⼯程系 ⼤⼆ (特選甲組)
● 熱愛競技程式設計、演算法、資料結構
● SYSTEX 精誠資訊 SEI 暑期實習⽣
● APCS 實作滿級分
● 台南⼥中資訊研究社 37 & 38th C++ 進階班講師
● 嘉義⼥中 111 學年度數理資優班 獨⽴研究資訊組 授課⽼師
● 2023 資訊之芽培訓計畫 南區算法班 講師
● 2022 ICPC Asia Taoyuan Regional Programming Contest Bronze Medal
動態規劃 Dynamic Programming

● 是⼀個把陣列名字叫做 dp 的技巧
○ 沒錯
● 是動態？還是規劃？
○ 他既⾮動態也⾮規劃
● 動態規劃是⼀個透過⼩的⼦問題解決⼤問題的技巧
○ 很像分治 (Divide and Conquer) ⼤事化⼩，⼩事化無
● 那為什麼叫動態規劃？
動態規劃 Dynamic Programming

● 我特別去找了⼀下資料，結果發明動態規劃的⼈的⾃傳有寫名⼦由來
● 發明動態規劃的⼈是 Bellman
● 他在他的⾃傳 《Eye of the Hurricane: An Autobiography》有提到
● 有興趣的可以參考 這個連結
● 為了給⼤家⼀點期待感我現在不想公布答案 : P
動態規劃 Dynamic Programming

● 動態規劃是什麼？
○ 在這邊我⽤⼀句話解釋動態規劃是什麼
■ ⻑江後浪推前浪，⼀替新⼈換舊⼈
○ 這句話呼應了動態規劃最核⼼的想法
○ ⽤以前的資訊來幫助我們得到當前最新的資訊
f(n) = f(n-1) + f(n-2)

● 可以把動態規劃想像成是⼀個公式
● 只要我們把公式需要的資訊先取得了，就可以慢慢往後推得後⾯的資訊
● f(0) = 0 , f(1) = 1
○ 有了以上這兩個資訊之後我們就可以依序算出 f(2), f(3) … f(n)
○ 求出 f(n) 的時間複雜度為 O(n)
f(n) = f(n-1) + f(n-2)

● 這樣⼦從底層往上慢慢推出後⾯資訊的⽅式稱為 Buttom-Up
● 與 Buttom-Up 相反的⽅式稱為 Top-Down
● 我們⼀樣來看這⼀個例⼦
f(n) = f(n-1) + f(n-2)

● 我們嘗試使⽤遞迴求得 f(n) 是多少

● 求得 f(n) 需要 f(n-1) 與 f(n-2) 的資訊
● 遞迴的終⽌條件則為 f(0) 與 f(1)
f(n) = f(n-1) + f(n-2)

● 這樣⼦的時間複雜度是 O(n) ㄇ？
● 我們畫出遞迴樹來看看
f(n) = f(n-1) + f(n-2)

● 你會發現有地⽅我們重複計算了
● 先前已經求過 f(2) 與 f(3) 了
f(n) = f(n-1) + f(n-2)

● 因此如果我們把之前算過的存起來
● 如果某次突然要使⽤到之前算過的資訊就可以直接拿出來⽤了
● 這就是動態規劃 Top-Down 的精神
時間複雜度？

● 因為這樣⼦我們可以保證這 n 個東⻄我們只會算過 1 次
● 時間複雜度⼜變回乾淨的 O(n) 了
Top-Down v.s Bottom-Up

● Top-Down 的缺點
○ 時間複雜度常數⼤
■ pass by value & pass by reference
■ 遞迴太深會導致 stack overflow
● Top-Down 的優點
○ 轉移式很直覺，只要記得把算過的存起來就好
Top-Down v.s Bottom-Up

● Bottom-Up 的缺點
○ 轉移式⽐較不直覺
● Bottom-Up 的優點
○ 寫起來很乾淨，時間複雜度常數⼩
● Bottom-Up 是動態規劃最常⾒的使⽤⽅法
● Top-Down ⼀個不⼩⼼遞迴太深就出⼤事了
排列組合動態規劃：CSES Problem Set Dice Combinations

● 骰⼦有 1 ~ 6 點，現在可以骰無限顆骰⼦，依序骰每⼀個骰⼦
● 求最後共有幾種骰法會使所有骰⼦的點數和為 n
● Example：
○ n = 3 , answer = 4
○ 1+1+1
○ 2+1
○ 1+2
○ 3
排列組合動態規劃：CSES Problem Set Dice Combinations

● 動態規劃的第⼀個步驟都是 定義轉移式
● 有點類似定義⼀個 Function 的概念
● 像是這題我們會定義 dp[i] = 骰出點數為 i 的組合數
排列組合動態規劃：CSES Problem Set Dice Combinations

● 定義完轉移式之後接下來就可以開始把公式推出來了
● 對於點數 i 來說，要使骰出的點數總和為 i ，會有 6 種可能
○ 點數 i - 6 時再骰出 1 個 6 點
○ 點數 i - 5 時再骰出 1 個 5 點
○ 點數 i - 4 時再骰出 1 個 4 點
○ and so on…
● 因此轉移式為 dp[i] = dp[i-1] + dp[i-2] + … + dp[i-6]
○ 加法原理
排列組合動態規劃：CSES Problem Set Dice Combinations

● 如此⼀來，很簡單的就可以⽤迴圈解決了，時間複雜度 O(n)
● 題⽬有說答案可能很⼤，只要輸出 mod 10^9 + 7 的結果就好
排列組合動態規劃：CSES Problem Set Coin Combinations I

● 有 n 種硬幣，每種硬幣的⾯額分別是 ci
● 接下來每⼀次你可以選擇其中⼀種硬幣 (可以重複拿⼀樣的)
● 求最後湊出總⾦額 x 的選法有幾種
排列組合動態規劃：CSES Problem Set Coin Combinations I

● 定義轉移式：dp[i] = 湊出總和為 i 的湊法有幾種

● 對於總和 i 來說，你有可能是透過：
○ i - c1 再拿 1 個 c1 硬幣得來的
○ i - c2 再拿 1 個 c2 硬幣得來的
○ i - c3 再拿 1 個 c3 硬幣得來的
○ and so on…
● 因此你會發現轉移式跟骰⼦那⼀題⼀樣
● 差別只在於骰⼦固定 1 ~ 6，硬幣是 c1 ~ cn
排列組合動態規劃：CSES Problem Set Coin Combinations I

● 對於每⼀個總和 i 我們都需要去枚舉 c1 ~ cn
● 因此整體時間複雜度為 O(nx)
● 我⾃⼰變數 x 是取名叫做 m
● 因為我⽐較叛逆⼀點
○ m 剛好在 n 旁邊
○ 打字會⽐較快
選擇困難的動態規劃：Atcoder DP Contest Frog 1

● 現在有⼀隻⻘蛙在第⼀個⽯頭，n 個⽯頭，每⼀個⽯頭的⾼度數字 hi
● 這⼀隻⻘蛙每⼀次只能跳 1 格或 2 格
● 如果原本在⾼度 a 的⽯頭，跳到⾼度 b 的⽯頭需要花費 | a - b |
● 求⻘蛙最後跳到第 n 個⽯頭所需要的最少花費
選擇困難的動態規劃：Atcoder DP Contest Frog 1

● 對於⻘蛙第 i 個⽯頭來說只有兩種可能
○ 從第 i - 1 個⽯頭跳過來
○ 從第 i - 2 個⽯頭跳過來
● 所以如果我們能算出跳到 i - 1 與 i - 2 的最佳答案，就可以求得跳到 i
的最佳答案
選擇困難的動態規劃：Atcoder DP Contest Frog 1

● 定義 dp[i] = 跳到 i 所需要的最⼩花費
● dp[1] = 0 , dp[2] = | h1 - h2 |
● 如果第 i - 2 個⽯頭的⾼度是 a , 第 i - 1 個⽯頭的⾼度是 b
● 從第 i - 2 個⽯頭跳過來所需花費為 dp[i-2] + | a - hi |
● 從第 i - 1 個⽯頭跳過來所需花費為 dp[i-1] + | b - hi |
選擇困難的動態規劃：Atcoder DP Contest Frog 1

● 要選出最好的⽅案，因此整個轉移式合併在⼀起就會變成：
● dp[i] = min( dp[i-2] + | a - hi | , dp[i-1] + | b - hi | )
● 整體時間複雜度 O(n)
選擇困難的動態規劃：Atcoder DP Contest Vacation

● Colten 放暑假只會做 3 件事情

○ 寫程式
○ ⽔餃
○ 睡覺
● 如果在第 i 天做第 1 件事情 Colten 會得到 ai 的快樂度
● 如果在第 i 天做第 2 件事情 Colten 會得到 bi 的快樂度
● 如果在第 i 天做第 3 件事情 Colten 會得到 ci 的快樂度
選擇困難的動態規劃：Atcoder DP Contest Vacation

● Colten 不會連續 2 天做同⼀件事情

● 求如果有 n 天，Colten 在最佳規劃下，快樂度最⼤可以是多少？
選擇困難的動態規劃：Atcoder DP Contest Vacation

● 對於每⼀天會有 3 種選擇
● 定義 dp[i][k] = 如果第 i 天做第 k 件事情能得到的最⼤快樂度
● dp[1][1] = a1 , dp[1][2] = b1 , dp[1][3] = c1
選擇困難的動態規劃：Atcoder DP Contest Vacation

● 對於 dp[i][1] 來說
○ 前⼀天 ( 第 i - 1 天 ) 不能也做第 1 件事情
● 對於 dp[i][2] 來說
○ 前⼀天 ( 第 i - 1 天 ) 不能也做第 2 件事情
● 對於 dp[i][3] 來說
○ 前⼀天 ( 第 i - 1 天 ) 不能也做第 3 件事情
選擇困難的動態規劃：Atcoder DP Contest Vacation

● 如果第 i 天要做第 1 件事情

○ 第 i - 1 天只能做第 2、3 件事情
○ 可以列出轉移式
■ dp[i][1] = max( dp[i-1][2] , dp[i-1][3] ) + ai
● 如果第 i 天要做第 2 件事情
○ 第 i - 1 天只能做第 1、3 件事情
○ 可以列出轉移式
■ dp[i][2] = max( dp[i-1][1] , dp[i-1][3] ) + bi
選擇困難的動態規劃：Atcoder DP Contest Vacation

● 如果第 i 天要做第 3 件事情

○ 第 i - 1 天只能做第 1、2 件事情
○ 可以列出轉移式
■ dp[i][3] = max( dp[i-1][1] , dp[i-1][2] ) + ci
選擇困難的動態規劃：Atcoder DP Contest Vacation

● 因此只要把每⼀天的所有選擇的最佳答案計算出來，就可以⼀直往後推
出最佳的答案
● 最後答案為 max( dp[n][1] , dp[n][2] , dp[n][3] )
● 時間複雜度：O(n)
0 / 1 背包問題

● 動態規劃當中最具代表性的問題之⼀
● ⽬前屬於 NP-Hard (還沒有找到多項式時間內的解法)
● 題⽬會給 n 個物品，容量 m 的背包
● 第 i 個物品會佔據背包 wi 的容量，價值為 vi
● 你的⽬標是最後讓背包裡的所有物品價值越⾼越好
0 / 1 背包問題

● 定義 dp[i][k] 表⽰考慮前 i 個物品的情況下，背包容量為 k 時所能得

到的最⼤價值
● 對於 dp[i][k] 來說，只有兩種選擇
○ 拿第 i 個物品
○ 不拿第 i 個物品
0 / 1 背包問題

● 如果我們要拿第 i 個物品，且當前背包只有 k 的容量

● 那在我們考慮前 i - 1 個物品時，背包容量只能有 k - wi
○ 因為拿第 i 個物品會佔據掉 wi 的容量
○ 如果在考慮前 i - 1 個物品時就⽤掉了超出 k - wi 的容量，第 i 個
物品是裝不下容量只有 k 的背包的
● 因此如果我們要拿第 i 個物品，轉移式為：
○ dp[i][k] = dp[i-1][k-wi] + vi
0 / 1 背包問題

● 如果我們不拿第 i 個物品，且當前背包只有 k 的容量

● 轉移式很簡單：
○ dp[i][k] = dp[i-1][k]
● 把這兩種可能的轉移式合併在⼀起就會變成
● dp[i][k] = max( dp[i-1][k] , dp[i-1][k-wi] + vi )
● ⽽我們最後要求的答案是 dp[n][m] ( n 個物品、背包容量 m )
● 因此我們就必須依序求出 dp[1][0~m], dp[2][0~m], … dp[n][0~m]
0 / 1 背包問題

● 求出 dp[i][0~m] 之前必須先把 dp[i-1][0~m] 求得

● ⽽我們已知 dp[0][0~m] 的結果都是 0
● 因此我們可以從底部開始推答案，推出 dp[n][m] 的結果
● 這就是動態規劃最重要的核⼼精神
● 整體時間複雜度：O(nm)
0 / 1 背包問題
無限背包問題

● 跟 0 / 1 背包問題要求的東⻄⼀樣
● 只是每⼀個物品的數量是無限的
無限背包問題

● 由於物品可以重複拿，我們的狀態就不⽤特別註明當前是考慮前幾種物
品，因此我們重新定義轉移式：
○ dp[i] = 背包容量為 i 時，所可以得到的最⼤價值
無限背包問題

● 對於容量 i 來說有 m 種可能

○ 在最⼤容量 i - w1 時再拿⼀個第 1 種物品
○ 在最⼤容量 i - w2 時再拿⼀個第 2 種物品
○ 在最⼤容量 i - w3 時再拿⼀個第 3 種物品
○ and so on…
● 你有發現ㄇ？是不是跟前⾯骰⼦還有硬幣那⼀題⼀樣了！
● 只差在最後要求的東⻄不⼀樣⽽已
無限背包問題

● 對於容量 i 來說拿第 k 個物品的話：

○ dp[i] = max( dp[i] , dp[i-w_k] + v_k )
● 整體時間複雜度：O(nm)
背包問題的瓶頸

● 時間複雜度我們可能無法改變，⽬前找不到什麼好⽅法
● 那我們來看看空間複雜度
背包問題的空間複雜度

● 需要開 n * m 的 dp 表格去紀錄 (除了無限背包有 O(m) 的作法)，因

此空間複雜度為 O(nm)
● DP 是⼀個⽤ 空間 換取 時間 的技巧
● 也就是說 n * m 如果太⼤，我們是完成不了 0/1 背包問題的
● 但其實 0/1 背包問題也有空間複雜度 O(m) 的作法
● 所以接下來我們來講 DP 當中的第⼀個優化技巧 滾動陣列
DP 優化：滾動陣列

● 如果⼀般的動態規劃是：
○ ⻑江後浪推前浪，⼀替新⼈換舊⼈
● 那麼被 滾動陣列 優化後的動態規劃就是：
○ ⻑江後浪推前浪，前浪死在沙灘上
DP 優化：滾動陣列

● 不是把陣列拿起來滾
● 滾動陣列的核⼼精神是：
○ 把沒有⽤到的陣列拿來繼續重複使⽤
● 其實就是有點資源回收的概念
DP 優化：滾動陣列

● 我們來看看 0/1 背包問題：

○ dp[i][k] = max( dp[i-1][k] , dp[i-1][k-wi] + vi )
● 有發現什麼事情ㄇ？
● 如果我們現在正在算 dp[5][0~m]
○ 那麼 dp[1][0~m], dp[2][0~m], dp[3][0~m] 以後都⽤不到了
○ 因為每⼀次轉移都只要知道前⼀次的結果
○ 這個時候滾動陣列這個技巧就可以派上⽤場了
DP 優化：滾動陣列

● 對於背包問題來說只需要記錄前 1 次的結果
● 我們就可以開兩組⻑度為 m 的陣列就好
○ 其中⼀組紀錄上⼀次的結果
○ 其中⼀組紀錄這⼀次轉移的結果
● 這樣的話空間複雜度就從 O(nm) 被我們優化成 O(m)
DP 優化：滾動陣列

● 我⾃⼰習慣把陣列開成 dp[2][m]
● 然後假設 i 是奇數時就表⽰ i - 1 是偶數，因此可以寫成
○ dp[i mod 2][k] = max( dp[ ( i - 1 ) mod 2 ][k] ,
dp[ ( i - 1 ) mod 2 ][k-wi] + vi )
0/1 背包甚⾄可以不使⽤⼆維陣列

● 因為每⼀次都是拿前 1 次的結果，⽽且結果是可以⼀直使⽤的不⽤清
空，所以其實 0/1 背包問題可以只開⼀維陣列解決
● 但是有個超級⼤的陷阱
0/1 背包甚⾄可以不使⽤⼆維陣列

● 如果我們寫成這樣會發⽣什麼事情？
0/1 背包甚⾄可以不使⽤⼆維陣列

● 如果我們寫成這樣會發⽣什麼事情？
● 假設 dp[10] 我們拿了第 1 個物品，這個物品的容量是 10
● 那如果我在轉移 dp[20] 的時候：dp[20] = dp[20-10] + v_1
● 我們重複拿了第 1 個物品 2 次！這是不合法的！
0/1 背包甚⾄可以不使⽤⼆維陣列

● 但是如果我們如果把第⼆個迴圈倒著回來？
● 我們每⼀次拿的資訊都是前⼀次的資訊，不會重複拿
● 這樣就完成⼀維陣列版本的 0/1 背包了
那這個是什麼背包？

● 我們剛剛說這樣⼦因為會重複拿同⼀個物品，不符合 0/1 背包
● 那什麼樣的背包問題可以重複拿同⼀個物品？
那這個是什麼背包？

● 我們剛剛說這樣⼦因為會重複拿同⼀個物品，不符合 0/1 背包
● 那什麼樣的背包問題可以重複拿同⼀個物品？
● 無限背包！因此無限背包也可以這樣寫
背包問題的變化？

● 背包問題的變形其實也很多
● 通常⽐賽遇到背包問題的題⽬都會被包裝的很精美
背包問題 - 改：平分問題

● 這其實也很常⾒了
● 有 n 個物品，每個物品的精美程度為 ai
● 現在必須把這 n 個物品分給某兩個⼈
● 你的⽬標是要讓最後這兩個⼈拿到的物品總精美程度的差越⼩越好
○ 講簡單⼀點：就是要盡可能讓兩個⼈的精美程度⼀樣
● 想想看這該怎麼做ㄅ
背包問題 - 改：平分問題

● 在最完美的情況下，兩個⼈的總精美程度都會是 ( a1 + … + an ) / 2
● 把題⽬轉成，給定 n 個物品，你的背包容量是 ( a1 + … + an ) / 2
● 每個物品的精美程度是 ai，佔據的空間也是 ai
● 求出這個背包最多能裝多少精美程度的物品
● 從這邊就可以發現，題⽬就變回⼀個很單純的 0/1 背包問題了
● 最後答案就會是 ( a1 + … + an ) / 2 - dp[ ( a1 + … + an ) / 2 ]
LIS: CSES Problem Set Increasing Subsequence

● 給定⼀個⻑度為 n 的序列 a
● 找出 a 序列的最⻑遞增⼦序列
● 相信 O(n^2) 的做法你們應該都會了，但可以做到 O(n * log n)
LIS: CSES Problem Set Increasing Subsequence

● 我們先複習 O(n^2) 的作法

● 定義 dp[i] 表⽰以 i 這個位置為結尾的 LIS ⻑度
● 我們從左到右求出 dp[i]
LIS: CSES Problem Set Increasing Subsequence

● 假設我們在求 dp[5]
● 那麼我們就去看看前⾯的 a[1] , a[2] , a[3] , a[4]
○ 如果 a[1] < a[5] , 那就 dp[5] = max( dp[5] , dp[1] + 1 )
○ 如果 a[2] < a[5] , 那就 dp[5] = max( dp[5] , dp[2] + 1 )
○ 如果 a[3] < a[5] , 那就 dp[5] = max( dp[5] , dp[3] + 1 )
○ 如果 a[4] < a[5] , 那就 dp[5] = max( dp[5] , dp[4] + 1 )
● 因為前⾯的 LIS 我們都已經求出來了，就想像成多接⼀個 a[5] 進去就
可以了
LIS: CSES Problem Set Increasing Subsequence

● 最後全部求完後記得答案不是 dp[n]，不要衝動
● 我們轉移式：dp[i] = 以 i 這個位置為結尾的 LIS ⻑度
● 因此答案為：max( dp[1] , … , dp[n] )
● 時間複雜度：O(n^2)
LIS: CSES Problem Set Increasing Subsequence

● 但這題的 n 範圍太⼤，O(n^2) 會 TLE，怎麼辦？

● 這個時候我們需要⼀個額外的演算法來輔助我們：
○ ⼆分搜尋 Binary Search
○ 貪婪演算法 Greedy Algorithm
LIS: CSES Problem Set Increasing Subsequence

● 我們額外開⼀個陣列 b
● 定義如果有⼀個⻑度為 i + 1 的 LIS，那麼把 b[i] 放在此 LIS 的最後
⼀個位置會是最⼩的數字
○ 如果我們能讓最後⼀個數字越⼩，表⽰我們成功的機會越⼤ (貪⼼)
○ 如果 b[2] = 3 , 那麼某個⻑度為 2 的遞增⼦序列可能是 ?, ?, 3
● ⼀開始 b 序列為 { }
LIS: CSES Problem Set Increasing Subsequence

● 我們從 a[0] ~ a[n-1]，每次看看 a[i] 可以被插⼊在 b 的什麼位置

○ 很像插⼊排序
● 假設 b = { 10,20,30 }，這個時候 a[i] = 13
● 我們就要將 b 改為 { 10,13,30 }
○ 因為在⻑度為 2 時，LIS 的最後⼀個數字選 13 是最⼩的
■ { 10 , 20 } and { 10 , 13 }
○ 只要讓選的數字越⼩越好，我們後⾯要構造⻑度更⻑的 LIS 就會更
容易構造
LIS: CSES Problem Set Increasing Subsequence

● 那如果 b = { 10,13,30 }，這個時候 a[i] = 40

● 就表⽰有⼀個當前最⼤的數字可以接在最後⾯
● 因此 b = { 10,13,30,40 }
LIS: CSES Problem Set Increasing Subsequence

● 怎麼求出最後答案的⻑度？
● 我們回想看看我們 b 陣列的定義：
○ 如果有⼀個⻑度為 i 的 LIS，那麼把 b[i] 放在此 LIS 的最後⼀個位
置會是最⼩的數字
● 那如果我們 b 陣列的⻑度是 k
○ 有⼀個⻑度 k 的 LIS，把 b[k-1] 放在這⼀個 LIS 會是最佳選擇
○ 換句話說存在這樣的⻑度為 k 的 LIS
○ 因此我們最後整個 a 序列的 LIS 為 k
LIS: CSES Problem Set Increasing Subsequence

● 在尋找插⼊點的這⼀個過程我們可以使⽤ ⼆分搜 來優化

● 整體的時間複雜度就會是 O(NlogN)
● 這⼀個求 LIS 的演算法稱為：Robinson-Schensted-Knuth Algorithm
有限背包問題

● 0/1 背包問題的改版
● 每⼀個物品可拆分
● 如果有⼀個物品的重量是 10 , 價格 100
● 可以把這個物品拆成兩個物品 A , B
● A 重量 2, 價格 20
● B 重量 8, 價格 80
有限背包問題

● 有限背包問題我們可以轉成 0/1 背包問題來解

● 但是需要⽤到⼆進位的概念
有限背包問題

● 如果有⼀個物品的重量是 97
● 那麼表⽰這個物品可能會被拆出 1, 2, 3, … , 96 這些重量
● 0/1 背包問題是 選 與 不選 之間做選擇
● 我們只要把物品拆分的聰明⼀點，被拆分的結果只要能組合出 1 ~ 97
● 這樣我們就可以直接當 0/1 背包問題解
有限背包問題

● 舉個例⼦來說：
○ 現在有⼀個物品重量 12
○ 我們如果拆成 1, 2, 4, 5
○ 這樣的話我們不管怎麼組合，都可以湊出 1 ~ 12 這些情況
○ ⼤家可以試試看 ><
有限背包問題

● 那我們應該如何聰明的拆？
● 12 的⼆進位是 1100
● 表⽰ 1 ~ 12 的⼆進位最多只會⽤到四個位置
● 那我們要先確保 2^2 , 2^1 , 2^0 存在
● 這樣如果數字的⼆進位⻑度只有 3，我們⼀定可以透過他們三個完成
有限背包問題

● 12 = 1100(2)
● 但為什麼我們不需要 2^3 = 8 ？
● 1 + 2 + 4 + 8 > 12
● 因此我們不可能拆成這樣
● 1 + 2 + 4 + ( 12 - ( 1 + 2 + 4 ) ) > 12 必須修改成這樣
● 但是這樣 8 ~ 11 這些數字我們構造的出來ㄇ？
有限背包問題

● 我們現在已經確定可以構造出 0 ~ 7 還有 12
● 7 + 5 = 12
● 6 + 5 = 11
● 5 + 5 = 10
● 4+5=9
● 3+5=8
● 因此 1, 2, 4, 5 這四個數字是可以湊出 0 ~ 12 任何⼀個數字的
有限背包問題

● 因此我們只要從 2^0, 2^1, 2^2 這樣⼀直給下去

● 直到給個東⻄的總和已經極限了之後再把剩下的補⿑
● 12 = 2^0 + 2^1 + 2^2 + 5 (補⿑)
● 把每個物品都做這件事情之後做⼀次 0/1 背包問題就可以了
有限背包問題

● 時間複雜度：？
● 空間複雜度：？
● ⼤家理解之後算算看吧！
概念類似：CSES Problem Set Missing Coin Sum

● 給定 n 個硬幣，每個硬幣都有專屬的⾯額
● 請求出最⼩的⾯額，這⼀個⾯額是不能透過這 n 個硬幣湊出來的
概念類似：CSES Problem Set Missing Coin Sum

● 將硬幣由⼩排到⼤
● 設⼀個變數 x，表⽰⽬前硬幣能湊出的最⼤⾯額為 x - 1
○ 換句話說，接下來的硬幣⾯額必須要是 1 ~ x
○ 否則如果硬幣⾯額是 x + 1，所有的硬幣就湊不出 x 了
● 從第⼀個硬幣試到最後⼀個硬幣
● 途中如果硬幣的⾯額 > x，就可以輸出答案了
● 時間複雜度：O(n * log n)
概念類似：CSES Problem Set Missing Coin Sum
有限背包問題：CSES Problem Set Book Shop II

● 練習看看有限背包問題吧！
⼀些無關的實戰：CF 765 pC. Road Optimization

● 難度 1700
● 有 n 個速度牌，每個速度牌上有數字
● 從起點開始，如果經過速度牌且該速度牌的數字是 x，接下來每單位花
費的時間就會是 x
⼀些無關的實戰：CF 765 pC. Road Optimization

● 現在你可選擇 0 ~ k 個速度牌並把他們拆掉
● 請你設計⼀個程式算出最少的花費時間
⼀些無關的實戰：CF 765 pC. Road Optimization

● 定義 dp[i][j] 表⽰在拆掉 j 個速度牌的情況下，⾛到第 i + 1 個速度牌

所需要花費的最少時間
⼀些無關的實戰：CF 765 pC. Road Optimization

● 第 0 個速度牌不能拆
● 第 n 個速度牌是指終點，實際上沒有速度牌
⼀些無關的實戰：CF 765 pC. Road Optimization

● 對於每⼀個速度牌有兩種可能
○ 把這個速度牌拆掉
○ 不要拆
⼀些無關的實戰：CF 765 pC. Road Optimization

● 對於到達第 i 個速度牌來說：
○ 他的前⼀個速度牌是誰？ (要枚舉)
○ 如果他的前⼀個速度牌是第 i - 3 個速度牌
○ 表⽰在這之間，有 2 個速度牌被拆了
⼀些無關的實戰：CF 765 pC. Road Optimization

● 到達第 i 個速度牌 ( 沒拆 i )，如果總共拆了 j 個速度牌 ( j 也要枚舉 )

○ 枚舉，如果是從第 p 個速度牌過來的
○ dp[i][j] = dp[k][ j - ( i - p - 1) ] + ( pos[i] - pos[p] ) * speed[p]
○ 如果總共拆 5 個且 p - i = 2 ，表⽰從起點到 p 拆了 3 個速度牌
⼀些無關的實戰：CF 765 pC. Road Optimization

● 最後答案就會是 min( dp[n][0] … dp[n][k] )

● 0 <= k <= n - 1
● 時間複雜度：O(n^3)
賽局動態規劃：CSES Problem Set Removal Game

● 給定⼀個⻑度 n 的序列，玩家有 2 個⼈
● 每⼀個⼈可以在每⼀個回合選擇序列的 頭 或 尾，並把該數字加到⾃⼰
的分數上，選擇後該位置的數字會消失
● 如果沒有數字可以拿了則遊戲結束
● 求出先⼿能得到的最⼤分數
○ 在兩位玩家都使⽤最佳策略的情形
賽局動態規劃：CSES Problem Set Removal Game

● 最佳策略的題⽬有⼀個重要的⼿筋，⼩技巧
● ⼀定要從 "最後" 做回 "最前"
● 我們必須要先能預測最後的結果，才能依靠這樣⼦的結果推得前⾯的最
佳策略，因此跟賽局有關的題⽬我們都必須反著做回來
賽局動態規劃：CSES Problem Set Removal Game

● 還有⼀個要注意的點，如果總分是 x
● 先⼿玩家在最佳策略下能得到 y 分
● 那麼後⼿玩家會得到 x - y 分
賽局動態規劃：CSES Problem Set Removal Game

● 定義 dp[L][R] 表⽰當序列只有 [ L , R ] 時，先⼿玩家能獲得的最佳分

數
● 在這樣的情況下先⼿玩家只能拿第 L 個數字或第 R 個數字
賽局動態規劃：CSES Problem Set Removal Game

● 假設先⼿玩家選第 L 個數字
● 表⽰原本的先⼿玩家變成了後⼿，另⼀個玩家⼀定會使⽤最佳策略讓對
⼿的分數越低，因此可以推出轉移式：
○ dp[L][R] = ( a[L+1] + … + a[R] ) - dp[L+1][R] + a[L]
賽局動態規劃：CSES Problem Set Removal Game

● 假設先⼿玩家選第 R 個數字
● 表⽰原本的先⼿玩家變成了後⼿，另⼀個玩家⼀定會使⽤最佳策略讓對
⼿的分數越低，因此可以推出轉移式：
○ dp[L][R] = ( a[L] + … + a[R-1] ) - dp[L][R-1] + a[R]
賽局動態規劃：CSES Problem Set Removal Game

● 這兩個式⼦取 max 就會是 dp[L][R] 的結果

● 但是在計算的過程要⼩⼼計算的順序
● dp[L][R] = ( a[L+1] + … + a[R] ) - dp[L+1][R] + a[L]
● dp[L][R] = ( a[L] + … + a[R-1] ) - dp[L][R-1] + a[R]
● 假設⽬前在算 dp[2][3]
○ dp[3][3] 跟 dp[2][2] 必須已經算完了
○ 第⼀個維度必須由⼤到⼩枚舉，第⼆個則是由⼩到⼤
賽局動態規劃：CSES Problem Set Removal Game

參考程式碼：[Link]
賽局動態規劃：ABC pD. Game in Momotetsu World

● 有兩個⼈在玩遊戲，遊戲在⼀個 n * m 的網格進⾏
● 兩個⼈的位置⼀樣，並且會同時⼀起移動
● 兩個⼈輪流決定如何移動，必須從 (1,1) ⾛到 (n,m)
● 只能往下⾛或往右⾛
● 採到 + 會加⼀分、反之採到 - 會扣⼀分
● 如果兩個⼈都採取最佳策略，請判斷誰會贏，或是回報平⼿
賽局動態規劃：ABC pD. Game in Momotetsu World

● ⽤跟剛剛⼀樣的概念，我們必須從最後往回推
● 定義 dp[i][j] 表⽰從 ( i , j ) ⾛到 ( n , m ) 第⼀個玩家能得到的分數
● 判斷⾛到 ( i , j ) 時，⽬前是誰的回合
● 當前位置如果是 ( i , j )，下⼀步可以到 ( i + 1 , j ) 或 ( i , j + 1 )
○ 因此跟 dp[i][j] 有關係的會是 dp[i+1][j] 跟 dp[i][j+1]
○ 如果當前是後⼿的玩家必須將兩者取 min，反之取 max
○ 先⼿玩家會盡量讓⾃⼰越好，後⼿要讓先⼿越差
賽局動態規劃：ABC pD. Game in Momotetsu World

● 剩下程式碼實作的部分⼤家練習看看吧！
● 時間複雜度：O(nm)
● 空間複雜度：O(nm)
積⽊型排組 DP：CSES Problem Set Counting Towers
積⽊型排組 DP：CSES Problem Set Counting Towers

● 狀況有點複雜，所以把某些情況分開會⽐較好處理
● 我們將整個積⽊分成左右兩半
● 定義 dp[i][0] 表⽰第 i 層的積⽊左右兩邊是屬於不同塊積⽊
● 定義 dp[i][1] 表⽰第 i 層的積⽊左右兩邊是屬於同⼀塊積⽊
積⽊型排組 DP：CSES Problem Set Counting Towers

● dp[1][0] = 1 , dp[1][1] = 1
● 可以推得：
○ dp[i][0] = dp[i-1][0] * 4 + dp[i-1][1]
○ dp[i][1] = dp[i-1][0] + dp[i-1] * 2
● 最後的答案就是 dp[n][0] + dp[n][1]
● 記得取 mod
動態規劃 - 狀態壓縮優化

● ⼀種把狀態透過另⼀種表⽰形式表現，讓 DP 可以更⽅便轉移的技巧
● ⼤部分題⽬都是將⼆進位狀態表⽰成⼗進位做轉移
○ 有些⼈會叫做位元 DP
● 很經典的例⼦：旅⾏推銷員問題
狀態壓縮 DP：CSES Problem Set Elevator Rides

● 有 n 個⼈要搭電梯，每⼀個⼈的重量為 ai
● 電梯每次可以載重量 k 單位
● 求把所有⼈載完最少需要幾次
狀態壓縮 DP：CSES Problem Set Elevator Rides

● n <= 20
● 但感覺⼜不能枚舉什麼東⻄？
● 這時候⼤⽅向就必須往位元 DP 這邊想了
狀態壓縮 DP：CSES Problem Set Elevator Rides

● 我們考慮⽤⼆進位的⽅式解決這題
● 0 表⽰不考慮這個⼈，1 表⽰考慮這個⼈
○ 101111 我們從右邊往左邊編號
○ 表⽰⽬前只考慮第 1、2、3、4、6 這幾個⼈
狀態壓縮 DP：CSES Problem Set Elevator Rides

● 對於 1011 的狀況來說，有三種可能
○ 原本電梯的狀況是：
■ 0011
■ 1001
■ 1010
● 因此我們如果知道在這三個情況的最佳答案，就可以推得 1011 這個
狀況的最佳答案
狀態壓縮 DP：CSES Problem Set Elevator Rides

● 如果從⼩數字做到⼤數字你會發現⼆進位剛好有⼀個特⾊
○ 對於 1011 來說：
■ 0011 算過了
■ 1001 算過了
■ 1010 算過了
狀態壓縮 DP：CSES Problem Set Elevator Rides

● 因此我們可以透過 bottom-up 的概念推出答案

● dp[i] 除了記錄次數之外，我們還必須額外紀錄⼀些東⻄：
○ first - 紀錄電梯使⽤次數
○ second - 最後⼀次的電梯重量最輕可以是幾公⽄
■ { 2 , 100 } 與 { 2 , 50 } 後者明顯⽐較好！
狀態壓縮 DP：CSES Problem Set Elevator Rides

● 要求的是 n 個⼈都搭電梯的答案
● 因此答案被存在 dp[(2^n)-1]