# 區間動態規劃 Dynamic Programming on Intervals
這篇要來介紹區間 DP，跟其他種 DP 一樣屬於把「某種東西」轉換成「狀態」的一種 DP，在這篇，就是將區間當成是一種狀態來做轉移
## 前情提要
### 動態規劃 Dynamic Programming
DP 代表動態規劃 (Dynamic Programming)，其中，Programming 的意思在這邊並不是我們所熟知到「寫程式」而是「規劃」，意旨規劃空間來解問題的技巧。值得注意的是，動態規劃不是一種演算法，而是一種設計演算法的「技巧」
### 狀態轉移
DP 的理解方式有很多種 (e.g. 分治法、遞迴...)。在這份筆記中，由於作者 ShanC 主要玩圖論較多，對於陣列的理解非常淺薄，因此習慣將 DP 解讀為一種「有向無環圖 (DAG)」，其中，每個邊就是一個操作、函數等等改變數值的方法，將較早拜訪的節點轉移到目標節點
當然，本篇要介紹的「區間」也可以表達為一種狀態
## 區間 Intervals
要討論區間，我們自然要先了解什麼是一個序列，避免一些先備知識的不足
||否則高中時的我肯定會看不懂||
### 序列 Sequence
序列，是用來表示有序列表的離散結構
ex : $\langle0, 1, 1, 2, 3, 5, 8, 13\rangle$
ex : $\langle\text{'h', 'e', 'l', 'l', 'o', '_', 'w', 'o', 'r', 'l', 'd'}\rangle$
### 索引編號 Indices
通常在競程，會給予序列中每一個元素「編號」，並且以陣列形式表達
|$i$|$0$|$1$|$2$|$3$|$4$|$5$|$6$|$7$|
|---|---|---|---|---|---|---|---|---|
|$A[i]$|$0$|$1$|$1$|$2$|$3$|$5$|$8$|$13$|
註 : 若編號從 $0$ 開始，稱為 $0$-based；若編號從 $1$ 開始，稱為 $1$-based
||如果之後遇到有人算數從 $0$ 開始數，那人十之八九是資工的||
### 區間 Intervals
區間指的是序列中的一段長，通常以兩個數字 $[L, R]$ (其中 $L\leq R$) 表達。中括號代表閉區間 (包含該元素)，小括號代表開區間 (不包含該元素)。但是在競程通常玩的都是離散的結構，中括號比較能精準表達
在競程，區間通常用於表達一個序列的**連續**子序列，由於要列出整個序列非常耗時，直接以區間表達會比較省事
ex : $\langle2, 3, 5, 8\rangle$ 是 $\langle0, 1, 1, 2, 3, 5, 8, 13\rangle$ 的一個**連續**子序列。若以 $0$-based 編號的區間表達，則分別為 $[3, 8]$ 與 $[0, 7]$
註 : 若有兩區間 $[L, R], [l, r]$，其中 $L\leq l$ 且 $r\leq R$，則 $[l, r]$ 是 $[L, R]$ 的子區間
## 區間 DP 陣列資料儲存
為了記錄區間需要兩個變數 $l, r$，所以通常使用二維的陣列 $dp[l][r]$ 來記錄區間 $[l, r]$ 的最佳解，其中，由於 $l \leq r$，因此實際上只會用到半個二維陣列。然而，這樣還不夠具體，如果能用圖來理解會更好
<center>
<img src="https://hackmd.io/_uploads/BJ2AnZzSgx.png" style="margin: 0 auto; display: block; width: 300px; height: 20px">
</center>
$~$
可以發現下半部完全用不到，這也是區間 DP 的一個小缺點，$O(n^2)$ 的空間實在有點大。如果覺得這張圖很複雜，那麼別擔心，因為這其實就只是陣列轉一下而已，但是在區間 DP，我們會特別強調從區間長度小到區間長度大，所以可以看成上圖那樣，從下處理到上的樣子
為了方便起見，以下部分全部會用 $1$-based 的編號來表示，因此陣列宣告時要開大一點
## 枚舉區間的方法
### 由左到右、由小區間到大區間
#### 先窮舉 $r$ 再窮舉 $l$
程式碼如下
```cpp
for(int r = 1; r <= n; r++){
for(int l = 1; l <= r; l++){
/*...your code...*/
}
}
```
若我們給一個 $1$-based 區間 $[1, 5]$，則窮舉的順序為 :
(外面的迴圈是直的、裡面的迴圈是橫的)
```cpp
l = 1 , l = 2 , l = 3 , l = 4 , l = 5
r = 1 : [1, 1],
r = 2 : [1, 2], [2, 2],
r = 3 : [1, 3], [2, 3], [3, 3],
r = 4 : [1, 4], [2, 4], [3, 4], [4, 4],
r = 5 : [1, 5], [2, 5], [3, 5], [4, 5], [5, 5]
```
#### 先窮舉 $l$ 再窮舉 $r$
程式碼如下
```cpp
for(int l = 1; l <= n; l++){
for(int r = l; r <= n; r++){
/*...your code...*/
}
}
```
若我們給一個 $1$-based 區間 $[1, 5]$，則窮舉的順序為 :
(外面的迴圈是直的、裡面的迴圈是橫的)
```cpp
r = 1 , r = 2 , r = 3 , r = 4 , r = 5
l = 1 : [1, 1], [1, 2], [1, 3], [1, 4], [1, 5],
l = 2 : [2, 2], [2, 3], [2, 4], [2, 5],
l = 3 : [3, 3], [3, 4], [3, 5],
l = 4 : [4, 4], [4, 5],
l = 5 : [5, 5]
```
### 由小區間到大區間、由左到右
$gap$ 代表 $l$ 與 $r$ 的距離，程式碼如下 :
```cpp
for(int gap = 0; gap <= n; gap++){
for(int l = 1, r = l + gap; r <= n; l++, r++){
/*...your code...*/
}
}
```
若我們給一個 $1$-based 區間 $[1, 5]$，則窮舉的順序為 :
(外面的迴圈是直的、裡面的迴圈是橫的)
```cpp
l = 1 , l = 2 , l = 3 , l = 4 , l = 5
gap = 1 : [1, 1], [2, 2], [3, 3], [4, 4], [5, 5],
gap = 2 : [1, 2], [2, 3], [3, 4], [4, 5],
gap = 3 : [1, 3], [2, 4], [3, 5],
gap = 4 : [1, 4], [2, 5],
gap = 5 : [1, 5]
```
### 遞迴 !?
遞迴也可以窮舉區間喔哈哈。但是因為太多種了，所以這邊只示範一種而已，這種方式是當我們不知道一個去列要去掉右邊還是去掉左邊時用的枚舉區間的方式。程式碼如下 :
```cpp
void sub_interval(int l, int r){
if(vis[l][r]) return;
vis[l][r] = true;
if(l == r) return;
sub_interval(l + 1, r);
sub_interval(l, r - 1);
}
```
若我們給一個 $1$-based 區間 $[1, 5]$，則窮舉的順序為 :
||這換行我也不知道要怎麼換，反正就這樣吧||
```cpp
[1, 5], [2, 5], [3, 5], [4, 5], [5, 5],
[4, 4],
[3, 4], [3, 3],
[2, 4], [2, 3], [2, 2],
[1, 4], [1, 3], [1, 2], [1, 1]
```
## 如何理解區間 DP ?
嚴格上來說，許多問題像是共同最長子序列 (LCS) 或是最長遞增子序列 (LIS) 都算是在區間上做 DP，但由於轉移方法與本篇有許多不同之處，所以還是來不嚴謹地定義一下，才不會討論到失焦。由於每個人理解的 DP 差異之大，所以還是把每種解釋列出來
### 解釋 1 : 列舉由小到大的區間
由於在上面已經有給各種枚舉區間的方法，事不宜遲，先給個求 $\begin{split} dp[l][r]=\sum_{i = l}^{r} i \end{split}$ 的程式碼
```cpp
for(int i = 1; i <= n; i++) dp[i][i] = i; // 這裡先初始化
for(int len = 1; len <= n; len++){
for(int l = 1, r = l + len; r <= n; l++, r++){
dp[l][r] = dp[l][l] + dp[l + 1][r];
}
}
```
如果對於程式碼夠敏感的話，應該很輕易理解，這就只是在做區間和的程式碼
若 $n$ 代入 $5$，可以得到
```cpp
[1, 1] : 1, [2, 2] : 2, [3, 3] : 3, [4, 4] : 4, [5, 5] : 5,
[1, 2] : 3, [2, 3] : 5, [3, 4] : 7, [4, 5] : 9,
[1, 3] : 6, [2, 4] : 9, [3, 5] : 12,
[1, 4] : 10, [2, 5] : 14,
[1, 5] : 15
```
不難發現，這就是在做區間和的程式碼其轉移狀態。如下圖所示，轉移越下面代表越小的子問題，所以是從下轉移到上，箭頭代表轉移方向。舉例來說，$[3, 5]$ 那格代表 $3$ 到 $5$ 的區間和
<center>
<img src="https://hackmd.io/_uploads/SJ4x76Mrge.png" style="margin: 0 auto; display: block; width: 300px">
</center>
$~$
補充說明 : 其實如果要求區間和，直接使用差分即可，區間 DP 只是方便舉例其轉移的原理而已。**若實際應用使用區間 DP 直接這樣求區間和會非常沒效率**
### 解釋 2 : 遞迴子區間 (分治法)
由於區間 DP 的題目很多都可以使用遞迴來推，這邊我們直接砸遞迴
```cpp
int find_max(int l, int r) {
if (dp[l][r] != -1) return dp[l][r];
if (l == r) return dp[l][r] = arr[l];
dp[l][r] = max(find_max(l + 1, r), find_max(l, r - 1));
return dp[l][r];
}
```
我們的目標是要求 $f(l, r)$，我們可以把問題切割成求 $f(l + 1, r)+f(l, r - 1)$，這樣也可以得到答案。此方法有以下性質 :
- Top-down approach
- Memoization : 若已經求過的答案，可以透過陣列 $dp$ 來判斷是否有算過
- 由於遞迴要用到許多空間，所以空間使用的效率差
使用這種區間 DP，我們去跑 $[1, 6]$ 可以得到以下結果 :
```cpp
[1, 1] : 5, [2, 2] : 4, [3, 3] : 1, [4, 4] : 6, [5, 5] : 3, [6, 6] : 9,
[1, 2] : 5, [2, 3] : 4, [3, 4] : 6, [4, 5] : 6, [5, 6] : 9,
[1, 3] : 5, [2, 4] : 6, [3, 5] : 6, [4, 6] : 9,
[1, 4] : 6, [2, 5] : 6, [3, 6] : 9,
[1, 5] : 6, [2, 6] : 9,
[1, 6] : 9
```
注意 : **這種方法只是舉例說明，實際運用時千萬不要用**
由於這種做法其實也是先遞迴到最小的問題，再去一路往大的解，所以大多也都可以改成迴圈的方法。等等的[例題](https://hackmd.io/@ShanC/interval-dp#%E5%B8%B8%E8%A6%8B%E4%BE%8B%E9%A1%8C%E8%AA%AA%E6%98%8E-3--CSES-Removal-Game)會用到這種方法
### 解釋 3 : 有向無環圖 (DAG) 的狀態轉移
我們在[這篇](https://hackmd.io/@ShanC/Intro-to-DP)說過，DP 都可以利用有向無環圖的表示，去走訪其順序，其順序就是拓樸排序。這種方式的理解較為抽象，簡單來說就是把每組 $[l, r]$ 看作一種狀態，然後如此一來就會形成有向無環的狀態圖。我們要的 DP 相當於最這張圖做[拓樸排序](https://hackmd.io/@ShanC/topological_sort)，其中有向邊就是轉移式。下圖為剛才[區間和](###解釋-1-:-列舉由小到大的區間)的例子所畫出的圖
<center>
<img src="https://hackmd.io/_uploads/Hyoo86fSlg.png" style="margin: 0 auto; display: block; width: 300px">
</center>
$~$
通常教科書中的 DP 都是以填表格來呈現，因此常會給人抽象的感覺，若是化成圖就會清晰許多。為了避免你覺得我把 DP 轉成 dag 是在胡說八道，這邊附上[連結](https://web.ntnu.edu.tw/~algo/DynamicProgramming.html)
我們都知道，DP 可以有 top-down 作法跟 bottom-up 作法，相同地，在區間 DP 也可以。以下用上述的[區間和](###解釋-1-:-列舉由小到大的區間)求解過程作為例子
#### Top-down
這邊我們先定義清楚，唯有「解完」該問題才算是拜訪該節點。所以，一開始就是 DFS 到 DFS 樹上的葉節點，接下來發現沒有鄰居了才離開，與 [DFS 版本的拓樸排序](https://hackmd.io/@ShanC/topological_sort#%E6%8B%93%E6%A8%B8%E6%8E%92%E5%BA%8F%E7%9A%84%E6%A9%9F%E5%88%B6-DFS)原理一模一樣 (但可能會只有拜訪完部分節點)。因此，走訪順序為 (先左再右) :
```cpp
1~5 : [1, 1], [2, 2], [3, 3], [4, 4], [5, 5],
6~9 : [4, 5], [3, 5], [2, 5], [1, 5]
```
會發現其實 top-down 只會計算該次呼叫所需要用到的所有子狀態，所以沒有跑滿所有狀態
#### Bottom-up
Bottom-up 就是一次把所有狀態都解完，走訪順序為 :
```cpp
1~5 : [1, 1], [2, 2], [3, 3], [4, 4], [5, 5],
6~10 : [1, 2], [2, 3], [3, 4], [4, 5], [1, 3],
11~15 : [2, 4], [3, 5], [1, 4], [2, 5], [1, 5]
```
對應到狀態圖，就是一組拓樸排序
## 常見例題說明 1 : [CF 608D - Zuma](https://codeforces.com/problemset/problem/608/D)
### 題目敘述
每一個長度為 $n$ 的序列 $c$，每次操作可以移除一段迴文，求最少要移除幾次才可把整個序列清空?
### 限制
- $1\leq n\leq 500$
- $1\leq c_i\leq n$
### 題解
區間 DP 的慣用手法就是先考慮長度最短的區間
- 考慮長度為 $1$ 的區間，要消除的話要花 $1$ 個步驟
- 考慮長度為 $2$ 的區間，若兩元素相同 (為迴文) 則需 $1$ 個步驟，否則需要 $2$ 個步驟
- 假設長度為 $k-2$ 與 $k-1$ 的區間已經找到最小操作次數，考慮長度為 $k$ 的區間 :
- 若兩邊的元素相同，則最佳答案就是去找不包含兩元素且長度為 $k-2$ 的區間，因為它有會變是迴文
- 若兩邊的元素不同，則最佳解就是將區間切成兩半找後的每種可能找最小
這樣講還是很抽象，所以你還是得自己想想看該怎麼理解比較好。或許利用上面給的三種區間 DP 的其中一種解釋會找到一種適合你的，找到一種對 DP 的理解方式比題目本身還重要。||以這題而言，我的理解其實就是數學歸納法||
### 實作程式碼
```cpp
for (int i = 1; i <= n; i++) dp[i][i] = 1;
for (int l = 1, r = 2; r <= n; l++, r++) {
if (arr[l] == arr[r]) dp[l][r] = 1;
else dp[l][r] = 2;
}
for (int len = 2; len <= n; len++) {
for (int l = 1, r = l + len; r <= n; l++, r++) {
for (int k = l; k + 1 <= r; k++)
dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
if (arr[l] == arr[r])
dp[l][r] = min(dp[l][r], dp[l + 1][r - 1]);
}
}
cout << dp[1][n] << '\n';
```
因為此方法是先從小區間擴張到大區間，所以我喜歡叫它擴張法
## 常見例題說明 2 : [Atcoder DP - Slimes](https://atcoder.jp/contests/dp/tasks/dp_n?lang=en)
### 題目敘述
給一個長度為 $N$ 的正整數序列 $a$。題目希望可以兩兩合併，合併後數值加總，目標是合併到只剩一個數字。求加總後的數字大可能為多少?
### 題目限制
- $2\leq N\leq400$
- $1\leq a_i\leq10^9$
### 題解
對於一個區間 $[l, r]$，我們並不知道該怎麼合併，所以可以試著問問看每個子區間是怎麼合併的，如此一來一路問到最小的區間 $[i, i]$ 就可以直接回傳答案。其中，區間的值會等於區間和。所以得到遞迴式
$\begin{split} f(l, r) = min_{k=l}^{r} \left\{ f(l, k) + f(k + 1, r) + \sum_{i=l}^{r} a_i \right\} \end{split}$
這遞迴式是先地回到最小問題，再一路解到大問題，因此也可以用迴圈來實作
最後答案會存在 $dp[1][n]$
這題邏輯容易卡在數字會重複加的這件事情，或許可以看看測資是怎麼處理的。AtCoder 原題的第一或第二個測資都會附上解釋，可以看參考參考
### 實作程式碼
$s[i]$ 為 $[1, i]$ 的區間和，可以利用這個鬼東西計算區間和
要注意這裡包了三層迴圈，複雜度為 $O(n^3)$
```cpp
for(int i = 0; i <= n; i++){
for(int j = 0; j <= n; j++)
dp[i][j] = INF;
}
for(int i = 1; i <= n; i++){
cin >> arr[i], s[i] += s[i - 1] + arr[i];
dp[i][i] = 0;
}
for(int len = 1; len <= n; len++){
for(int l = 1, r = len; r <= n; l++, r++){
for(int k = l; k < r; k++)
dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + (s[r] - s[l - 1]));
}
}
cout << dp[1][n] << '\n';
```
## 常見例題說明 3 : [CSES Removal Game](https://cses.fi/problemset/task/1097/)
### 題目敘述
給一個長度為 $n$ 的整數陣列 $x$。兩玩家玩遊戲 : 每回合輪流取走頭或尾其中一個數字加到分數，雙方都希望分數總和最大。請問第一位玩家最多可能拿到多少分數?
### 題目限制
- $1\leq n \leq 5000$
- $-10^9\leq x_i\leq 10^9$
### 題解
我們並不知道在一開始，區間 $[1, n]$ 要怎麼解，所以可以試圖拆解問題 :
- 由於這是個[零和賽局](https://en.wikipedia.org/wiki/Zero-sum_game)(結果不是你贏就是我贏)，所以可以計算 payoff，就是我的分數總合減去對方的分數總合
- 假設陣列只有一個數字，則該回合玩家只能選擇該數字
- 假設陣列只有兩個數字 $a, b$，該回合玩家會選擇最大值，也就是 $max(a, b)$
- 若想要找到 $[1, n]$，那麼就要比較到底是取 $[1]$ 的 payoff 比較高還是取 $[n]$ 的 payoff 比較高
- 令 $dp[l][r]$ 為區間 $[l, r]$ 的最佳解
- 假設我們已經知道 $[1, n - 1]$ 與 $[2, n]$ 的最佳解，也就是前一位玩家的最佳解。考慮下一位玩家要取 $[1, n]$ 的最佳 payoff 就會是去比較 $x_1 - dp[2][n]$、$x_n - dp[1][n-1]$ 誰比較大
設第一位玩家的總和是 $p$、第二位是 $q$。由於第一位玩家取的時候，一定會是區間 $[1, n]$，因此第一位玩家的 payoff 就是 $p-q = dp[1][n]$ (根據上面定義 payoff 的計算方法)。然後，$\sum x_i=p+q$，因為分數一定全部分到兩人手上。所求 $p=\cfrac{dp[1][n]+\sum x_i}{2}$
### 小提醒
若是只取當前**分數總合最高**的選項，而非 **payoff 最高**，會有機會使對方取到更高分數
ex : 假設當前序列為 $\langle8, 20, 1, 2\rangle$，當前若取了最大值 $8$，則會使對方在下一回合取到 $20$。因此，最佳策略應該是第一個玩家取 $2$，接下來第二個玩家只能取到 $8$、$1$，而第一個玩家可以取到 $20$
||若想更了解零和賽局，可以去學學看賽局理論 (博弈論)。我修過這門課，很好玩喔!!||
### 解法 1 : 分治法
若看成 top-down，顯然是分治法 (也可以理解成遞迴)。若看成 bottom-up 就是用迴圈
```cpp
/* 以上略 */
long long f(int l, int r){
if (dp[l][r] != -1) return dp[l][r];
if (r-l <= 1) return dp[l][r] = max(a[l], a[r]);
dp[l][r] = a[l] + pre[r] - pre[l] - f(l+1, r);
dp[l][r] = max(dp[l][r], pre[r-1] - pre[l-1] - f(l, r-1) + a[r]);
return dp[l][r];
}
/* 以下略 */
// code from Yui Huang 演算法學習筆記
```
註 : 這在 2020 年的時候還可以 AC，現在有新測資就不能了，猜應該是遞迴吃太多時間 (or 空間)
### 解法 2 : 迴圈
如果你前面都有看懂，要轉化成這副模樣就不難了!!
```cpp
cin >> n;
for(int i = 1; i <= n; i++) // 處理輸入與總和
cin >> arr[i], dp[i][i] = arr[i], total += arr[i];
for(int len = 1; len <= n; len++){ // 處理狀態轉移
for(int l = 1, r = l + len; r <= n; l++, r++)
dp[l][r] = max(arr[l] - dp[l + 1][r], arr[r] - dp[l][r - 1]);
}
cout << (total + dp[1][n]) / 2 << '\n';
```
## 題目練習
[Atcoder Educational DP Contest N - Slimes](https://atcoder.jp/contests/dp/tasks/dp_n?lang=en) (基礎題)
[Zerojudge d686. 10003 - Cutting Sticks](https://zerojudge.tw/ShowProblem?problemid=d686) (基礎題)
[Zerojudge e898. 抽抽樂 獎不完](https://zerojudge.tw/ShowProblem?problemid=e898) (基礎題)
[Zerojudge o188. Q-6-18. 矩陣乘法鏈](https://zerojudge.tw/ShowProblem?problemid=o188) (演算法課本就有的基礎題)
[Zerojudge d273. 11584 - Partitioning by Palindromes](https://zerojudge.tw/ShowProblem?problemid=d273) (可以先判斷一個子字串否為迴文)
[CSES Removal Game](https://cses.fi/problemset/task/1097) (賽局，自己的 payoff 就是自己的分數減對方的分數，拿 payoff 做 DP)
[Atcoder Educational DP Contest L - Deque](https://atcoder.jp/contests/dp/tasks/dp_l) (Déjà vu ?)
[Codeforces 1114D - Flood Fill](https://codeforces.com/problemset/problem/1114/D) (或許跟 LCS 有關?)
[Zerojudge r407. 10617 Again Palindromes](https://zerojudge.tw/ShowProblem?problemid=r407) (EZ)
[AtCoder Grand Contest 021 D - Reversed LCS](https://atcoder.jp/contests/agc021/tasks/agc021_d) (延續 CF 1114D，迴文??LCS??區間DP??)
[Codeforces 608D - Zuma](https://codeforces.com/problemset/problem/608/D) (擴張法??)
[Codeforces 1509C - The Sports Festival](https://codeforces.com/problemset/problem/1509/C) (貪心 + 前面的賽局題)
[Codeforces 1132F - Clear the String](https://codeforces.com/problemset/problem/1132/F) (擴張法??)
[2020 ICPC 台灣站 pE](https://codeforces.com/gym/102835/problem/E)
[Codeforces 1312E - Array Shrinking](https://codeforces.com/contest/1312/problem/E) (可以考慮用兩個陣列維護答案與區間顏色)
[AtCoder Beginner Contest 325 G - offence](https://atcoder.jp/contests/abc325/tasks/abc325_g) (找到 `'o'` 之後找 `'f'`，再窮舉後面的長度)
----
## 參考資料
[海大競程 - DP (單調隊列、區間DP)](https://hackmd.io/@LeeShoWhaodian/rJHXNrlNel#/)
[師大演算法筆記 - dynamic programming](https://web.ntnu.edu.tw/~algo/DynamicProgramming.html)
[Yui Huang 演算法學習筆記 - 【題解】CSES 1097 Removal Game](https://yuihuang.com/cses-1097/)
----
> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2025/7/5
Sign in with Wallet
Connect another wallet