讓我們來看看以下例題：
Palindromic Distance
給定一個字串 $s$，你可以對這個字串進行以下三種操作：
- 插入一個字元
- 刪除一個字元
- 將一個字元替換成另一個字元
求最少要做幾次操作才可以讓這個字串變成迴文？
舉例來說，若 $s$ 是 hello，可以使用以下幾種方法來在兩次操作內將其轉成迴文：
hello$\stackrel{\text{刪除}}{\longrightarrow}$ello$\stackrel{\text{替換}}{\longrightarrow}$ollohello$\stackrel{\text{刪除}}{\longrightarrow}$hllo$\stackrel{\text{替換}}{\longrightarrow}$hllhhello$\stackrel{\text{插入}}{\longrightarrow}$helloh$\stackrel{\text{替換}}{\longrightarrow}$helleh
條件限制
- 至多 $t \leq 200$ 筆測資。
- 字串長度總和 $\leq 3000$。
這種題目該如何定義狀態呢？如果令 $dp[i]$ 是考慮長度 $i$ 前綴的最佳解，好像完全不知道怎麼轉移。
這時候就是區間 DP 登場的時候了，我們用以下的方式來定義狀態：
- $dp[l][r]$ 代表考慮 $s$ 區間 $[l, r]$ 的子字串時，最少要做幾次操作才能將其轉成迴文。
為什麼會這樣定義狀態呢？可以注意到，檢查迴文這個過程其實可以想成是「先確保字串頭尾一樣之後，再往內一格確保裡面是迴文」的過程，因此有個自然的子結構就出現了！
因此，這時如果我們要計算 $dp[l][r]$ 的答案，就會有以下幾種候選操作來對應到子問題：
- 頭尾已經一樣了，直接取得 $dp[l + 1][r - 1]$ 的值。
- 頭尾不一樣的話：
- 插入尾端的字元在最左邊、或是刪除尾端的字元，花費為 $dp[l][r - 1] + 1$。
- 插入前端的字元在最右邊、或是刪除前端的字元，花費為 $dp[l+1][r] + 1$。
- 花費一次替換來讓頭尾一樣，花費為 $dp[l+1][r-1]+1$。
因此轉移式就可以寫成
$$
dp[l][r] = \begin{cases}
dp[l+1][r-1] & s[l] = s[r] \\
\min(dp[l][r-1], dp[l+1][r], dp[l+1][r-1]) + 1 & s[l] \neq s[r]
\end{cases}
$$
就可以獲得一個 $O(N^2)$ 的作法了！
我們試試看用另一道題目來讓讀者感受一下區間 DP 的魅力。下面這道例題也是非常典型的一個例子，又被稱作「最小矩陣鏈乘積」。
矩陣鍊 mystery
上了大學之後，JOI 君修了一門叫做線性代數的課，裡面常常用到矩陣乘法。
假設有矩陣 $A, B$ 其中 $A$ 是個 $n \times m$ 大小的矩陣，且 $B$ 是個 $m \times k$ 大小的矩陣。
那 $AB = C$ ，$C$ 是個 $n \times k$ 大小的矩陣，並且我們需要做 $nmk$ 那麼多次的運算才能夠算出 $C$。
不只如此，矩陣乘法是有結合律的，也就是說 $A(BC) = (AB)C$。
JOI 君拿到了一份作業，題目如下。
給定 $N$ 個矩陣 $A_1, A_2,\ldots,A_N$ 請問 $A_1A_2\ldots A_N$ 為多少？
看到之後 JOI 君瑟瑟發抖，因為計算量實在太龐大了。
JOI 君發現，因為結合律的關係，只要改變計算順序就有可能省下一些計算量。
聰明的你，可不可以告訴 JOI 君，在最佳狀況下，需要幾次運算才能得到答案呢？
本題會以下列格式輸入：
輸入第一行為一個正整數 $N$ 代表總共有幾個矩陣。
接下來一行有 $N+1$ 個正整數以一個空白隔開 $B_1, B_2,\ldots,B_N, B_{N+1}$。
代表說，第 $i$ 個矩陣是 $B_i \times B_{i+1}$ 的矩陣。
條件限制
- $N\leq 1000$
- $B_i \leq 1000$
既然我們都說要用區間 DP 了，那考慮以下狀態：
- $dp[l][r]$ 代表將 $B_l, B_{l+1}, ..., B_r$ 所形成的矩陣，也就是 $A_l, A_{l+1}, \dots, A_{r-1}$ 乘起來的最小花費。
轉移……咦，要怎麼轉移啊？
這種類型題目的「子結構」其實稍微不直覺一點，我們需要用到解題時的一種技巧：反過來想。
在把所有矩陣乘起來的過程，其實可以想成是每次把三個連續數字 $a, b, c$ 選起來，用 $abc$ 的花費把中間的 $b$ 刪掉。因此，整個乘法過程的最後一步，肯定是有某個在中間的 $i$ 留到了最後，並把 $B_1, B_i, B_{N+1}$ 選起來之後、再把 $i$ 刪除來結束整個過程。
那這不就表示，$B_1\sim B_i$ 之間、和 $B_i\sim B_{N+1}$ 之間形成了兩個獨立的子問題嗎？
- 此時對應的花費就是 $B_1B_iB_{N+1} + dp[1][i] + dp[i][N+1]$！
因此，如果用最後一步的視角去想，我們只需要窮舉最後被刪掉的數字是誰，並依序得到對應的子問題花費後，再取最小值就是答案了！
轉移式寫起來就會長得像這樣：
$$
dp[l][r] = \min_{l < i < r}\{B_lB_iB_{N+1} + dp[l][i] + dp[i][r]\}
$$
此時我們就得到 $O(N^3)$ 的演算法了！
雖然這題的 $N$ 有到 $1000$，但上述的區間 DP 演算法的常數其實非常小，是能穩定通過的喔！
不過這題其實也有 $O(N\log N)$ 的演算法就是……但超出目前的內容許多，建議非常有興趣再上網查查看。
上面我們講完了兩道例題，如果要試圖寫解的話，最直觀的作法當然是使用 top-down 沒錯，但還是會擔心常數太大。要怎麼使用 bottom-up 實作呢？
回想動態規劃的必要元素所提到的，動態規劃的過程必須滿足「無後效性」，所以我們要找到一個計算 DP 的順利來讓我們可以在轉移的過程中不會存取到還沒算好的值。
一個直覺的方法是發現，區間 DP 的轉移其實都是取「長度更短」的區間所對應到的 DP 值，所以其實有種很自然的寫法是像下面這樣：
for (int len = 1; len <= n; ++len)
for (int l = 1; l + len <= n + 1; ++l) {
int r = l + len - 1;
// calculate dp[l][r]
}不過其實有另一種相對不直覺但其實意外好寫的作法是這樣的：
for (int r = 1; r <= n; ++r)
for (int l = r - 1; l >= 1; --i) {
// calculate dp[l][r]
}也就是以 $r$ 遞增、$l$ 遞減的順序來計算，讀者可以思考看看為什麼這樣就可以保證在轉移的過程中不會取到還沒計算完的值。
這種寫法其實比想像中還要厲害，甚至有些未來的 DP 優化題會需要利用這個計算順序來處理。
另外再提一下，其實我們這次整篇文章都沒有提到這些區間 DP 的 base case 要怎麼定義，這部分就交給讀者思考了。
我們在這篇文章帶讀者看了兩種類型的題目，其實概念上可以分成以下兩種狀況：
- 題目所求很自然的適合用「區間」當成子結構來建構。例如前面提到的迴文就是一種。
- 把題目倒過來想之後，會發現拿掉最後一步後，題目會自然的被分裂成可以用區間來代表的子問題。
當然，這只是比較初步的分類方式，實際上這些狀況的本質都還是發現「題目的結構可以用區間表示」，至於要怎麼發現這樣的性質，就是對選手觀察力和經驗上的考驗了。
最後補充一點，這種「以區間為狀態」的想法，其實也可以擴充到「用子矩形當狀態」，具體會是以哪種方式呈現，就交給讀者在習題自行領悟吧！
Cutting Sticks
你的任務是替一家叫 Analog Cutting Machinery (ACM) 的公司切割木棍。切割木棍的成本是根據木棍的長度而定。而且切割木棍的時候每次只切一段。
很顯然的，不同切割的順序會有不同的成本。例如：有一根長 $10$ 公尺的木棍必須在第 $2, 4, 7$ 公尺的地方切割。這個時候就有幾種選擇了。你可以選擇先切 $2$ 公尺的地方，然後切 $4$ 公尺的地方，最後切 $7$ 公尺的地方。這樣的選擇其成本為：$10+8+6=24$。因為第一次切時木棍長 $10$ 公尺，第二次切時木棍長 $8$ 公尺，第三次切時木棍長 $6$ 公尺。但是如果你選擇先切 $4$ 公尺的地方，然後切 $2$ 公尺的地方，最後切 $7$ 公尺的地方，其成本為：$10+4+6=20$，這成本就是一個較好的選擇。
你的老闆相信你的電腦能力一定可以找出切割一木棍所需最小的成本。
條件限制
- 木棍的長度 $\leq 1000$。
- 會有至多 $50$ 需要切割的地方。
合併成本
有 $n$ 個數字排成一列，依序是 $a[1], a[2], a[3], \cdots, a[n]$。
每次可以挑選兩個相鄰的數字 $(u, v)$ 合併，合併會花費 $|u-v|$ 元，合併起來的數字會變為 $u+v$。
問把 $n$ 個東西合成一個數字的最小花費是多少？
條件限制
- $1\leq n\leq 100$
趙哥愛妹子
給你一個 $n\times m$ 的數字表格，一開始所有的點都是白色，每次可以選一個點從該點往四方向延伸的十字塗黑，每個方向可以不斷延伸直到撞到一個已塗成黑色的格子為止，花費會是該次塗色的所有格子之數字總和乘上選擇的點的數字。
試求將所有格子塗黑的最小花費。
條件限制
- $n, m\leq 40$
彩色紙條
雷文想要把一張紙條用油彩塗上顏色。這張紙條上面有 $N$ 個格子，依序編號為 $1$ 到 $N$，一開始都是白色（編號為 $0$），而雷文不喜歡白色，想要用編號為 $1$ 到 $M$ 的 $M$ 種顏色塗紙條，並把其中第 $i$ 格塗上某個非白色的顏色 $c_i$（編號大於 $0$ 而不超過 $M$）。
雷文上色的時候，每次可以一筆畫把連續若干格塗上顏色，並且覆蓋過原先塗在格子上的顏色。舉例來說，如果一個紙條上面有 $5$ 格，顏色依序為 $(1,1,1,2,2)$，那麼雷文可以一筆畫把第 $2$ 格到第 $4$ 格塗上顏色 $3$，使紙條顏色變成 $(1,3,3,3,2)$。雷文決定好自己想要把紙條塗上那些顏色之後，想要用最少的次數完成塗色。例如雷文想要把有 $5$ 個的紙條塗上 $(1,2,3,2,1)$，最少需要三次：先把第 $1$ 格到第 $5$ 格塗上顏色 $1$，再把第 $2$ 格到第 $4$ 格塗上顏色 $2$，最後把第 $3$ 格塗上顏色 $3$。過程如下：$$(0,0,0,0,0) \to (1,1,1,1,1) \to (1,2,2,2,1) \to (1,2,3,2,1)$$這是最少次數的塗法。請幫他撰寫一個程式，依據雷文的喜好，算出最少要塗幾次才能夠完成。
條件限制
- $1\leq N\leq 200$
- $1\leq M\leq 200$
- 至多 $T\leq 20$ 筆測資。
最長共同回文子序列
給定兩個長度分別為 $N, M$ 的字串 $a, b$，請輸出滿足以下條件的字串 $c$ 的長度：
- $c$ 為 $a$ 的子序列
- $c$ 為 $b$ 的子序列
- $c$ 為回文字串
- $c$ 為所有滿足以上三條的字串中最長的
定義 $|s|$ 為 $s$ 的長度。
字串 $t$ 為字串 $s$ 的子序列若存在一個序列 $a_1, a_2, \ldots, a_{|t|}$ 滿足 $1 \leq a_1 < a_2 < \ldots < a_{|t|} \leq |s|$ 且 $t_i = s_{a_i} \forall 1 \leq i \leq |t|$。
字串 $s$ 為回文字串若 $s_i = s_{|s| + 1 - i} \forall 1 \leq i \leq |s|$。
條件限制
- $1\leq N, M\leq 80$
A Color Game
給定一個長度為 $n$ 的字串，每次可以刪除一個長度不超過 $m$、且字元完全相同的區間，刪除完後字串剩餘的部分會接起來，問是否有可能將整個字串刪除。
條件限制
- $n,m \leq 500$