一、前言

??區間DP又名區間動態規劃，在 LeetCode 上屬于難度中上的題，而 ACM 競賽中屬于簡單級別，為必須掌握的內容，實際思想也比較簡單，基本上看完我寫的總結，大部分題目都可以用模板套出來了，
??區間DP的狀態設計相對簡單，基本大部分問題都是用 f [ i ] [ j ] f[i][j] f[i][j] 代表區間 [ i ， j ] [i，j] [i，j] 上的最優解，難點在于狀態轉移的設計上，本文將通過一些例題，詳細講解常見的狀態轉移套路，
??對于區間DP來說，一個最經典的思想就是正難則反，聽我娓娓道來，

二、石子歸并

• 石子歸并問題，基本上是所有講解 區間 DP 的文章都會提到的一個題，那么我也不例外，

【例題1】有 n ( n ≤ 100 ) n(n \le 100) n(n≤100) 堆石子擺放成一排，第 i i i 堆的重量為 w i w_i wi?，現要將石子有次序地合并成一堆，規定每次只能選相鄰的二堆合并成新的一堆，合并的消耗為當前合并石子的總重量，試設計出一個演算法，計算出將 n n n 堆石子合并成一堆的最小消耗，

• 在思考用動態規劃求解的時候，我們可以先想想如果窮舉所有方案，會是什么情況，

1、窮舉

• 對于這個問題來說，我們第一個決策可以選擇一對相鄰石子進行合并，總共有 n ? 1 n-1 n?1 種情況；對于 5堆 石子的情況，第 1 次合并總共有 4 種選擇：
• 1）選擇 第 1 堆 和 第 2 堆 的石子進行合并，如圖二-1-1所示：
  圖二-1-1
• 2）選擇 第 2 堆 和 第 3 堆 的石子進行合并，如圖二-1-2所示：
  圖二-1-2
• 3）選擇 第 3 堆 和 第 4 堆 的石子進行合并，如圖二-1-3所示：
  圖二-1-3
• 4）選擇 第 4 堆 和 第 5 堆 的石子進行合并，如圖二-1-4所示：
  圖二-1-4
• 以上任意一種情況都會把石子變成 4 堆，然后就變成了求解 4 4 4 堆石子的問題；我們可以采用同樣方法，把石子變成 3 3 3 堆， 2 2 2 堆，最后變成 1 1 1 堆，從而求出問題的最終解，
• 當然，這是一個遞回的程序，每次合并可以將石子堆數減一，總共進行 n ? 1 n-1 n?1 次合并，每個階段可行的方案數都是乘法的關系，窮舉的方案總數就是 ( n ? 1 ) ! (n-1)! (n?1)!；
• 例如，上面提到的剩下的這 4 堆石子，采用深度優先搜索列舉所有可行解的搜索樹如圖二-1-5所示：
  圖二-1-5
• 圖中用 ‘-’ 表示不同堆石子之間的分隔符，即 1-2-3-4 代表 4 堆的情況，12-3-4表示 第 1 堆 和第 2 堆 合并后的情況，
• 對這么多種方案取總消耗最小的，正確性是一定可以保證的，因為我們列舉了所有情況，然而時間上肯定是無法接受的，
• 那么，如何來優化搜索呢？
• 我們發現這個問題的難點在于：當選出的兩堆石子合并以后，它的重量變成了合并后的和，對于 n n n 堆石子，選擇的 n ? 1 n-1 n?1 種合并方式，到達的都是不同的狀態，無法進行狀態存盤，

2、正難則反

• 當沒有頭緒的時候，我們試著將問題反過來思考；
• 我們發現這棵深度優先搜索樹的所有葉子結點都是一樣的，這就為我們解決問題帶來了突破口；
• 對于 [ 1 , n ] [1, n] [1,n] 堆石子，假設已經合并了 n ? 2 n-2 n?2 次，必然只剩下 二堆石子，那么我們只需要合并最后一次，就可以把兩堆石子變成一堆，假設合并最后一次的位置發生在 k k k，也就是最后剩下兩堆分別為： [ 1 , k ] [1, k] [1,k] 和 [ k + 1 , n ] [k+1, n] [k+1,n]，如圖二-2-1所示：

• 注意，這個時候 [ 1 , k ] [1, k] [1,k] 和 [ k + 1 , n ] [k+1, n] [k+1,n] 已經各自合并成一堆了，所以我們把問題轉換成了求 [ 1 , k ] [1, k] [1,k] 合并一堆的最小消耗，以及 [ k + 1 , n ] [k+1, n] [k+1,n] 合并成一堆的最小消耗；而這里 k k k 的取值范圍為 [ 1 , n ? 1 ] [1, n-1] [1,n?1]；
• 利用這樣的方法，逐步將區間縮小成 1，就可以得到整個問題的解了，

3、設計狀態

• 令 f [ i ] [ j ] f[i][j] f[i][j] 表示從 第 i i i 堆 石子到 第 j j j 堆 石子合并成一堆所花費的最小代價，

4、狀態轉移方程

• f [ i ] [ j ] = { 0 i = j min ? k = i j ? 1 ( f [ i ] [ k ] + f [ k + 1 ] [ j ] + c o s t ( i , j ) ) i ≠ j f[i][j] = \begin{cases} 0 & i=j\\ \min_{k=i}^{j-1}(f[i][k] + f[k+1][j] + cost(i,j)) & i \neq j\end{cases} f[i][j]={0mink=ij?1?(f[i][k]+f[k+1][j]+cost(i,j))?i=ji?=j?
• 其中 c o s t ( i , j ) = ∑ k = i j w k cost(i, j) = \sum_{k=i}^{j}w_k cost(i,j)=∑k=ij?wk?
• 有了上面 “正難則反” 的解釋，這個狀態轉移方程就很好理解了；
• 1）當 i = j i=j i=j 時，由于 f [ i ] [ j ] f[i][j] f[i][j] 已經是一堆了，所以消耗自然就是 0 了；
• 2）當 i ≠ j i \neq j i?=j 時，我們需要把目前剩下的兩堆合并成一堆，一堆是 f [ i ] [ k ] f[i][k] f[i][k] ，另一堆是 f [ k + 1 ] [ j ] f[k+1][j] f[k+1][j]，這兩堆合并的消耗就是 從 第 i i i 堆到第 j j j 堆的重量之和，即 c o s t ( i , j ) = ∑ k = i j w k cost(i, j) = \sum_{k=i}^{j}w_k cost(i,j)=∑k=ij?wk?，而對于合并方案，總共 k = j ? i k=j-i k=j?i 種選擇，所以列舉 j ? i j-i j?i 次，取其中最小值就是答案了，
• 通過記憶化搜索求解 f [ 1 ] [ n ] f[1][n] f[1][n] 就是最后的答案，
• 以上就是最經典的區間 DP 問題，

三、區間DP的特征

1、狀態設計

• 利用區間來描述狀態，所以一般情況下都可以用 f [ i ] [ j ] f[i][j] f[i][j] 作為 DP 陣列，其中 i , j i, j i,j 為問題對應的區間 [ i , j ] [i, j] [i,j] 的左右端點；
• 當然，有的時候需要一個輔助維，狀態可能會設計成 f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k] ，其中 i , j i, j i,j 為問題對應的區間 [ i , j ] [i, j] [i,j] 的左右端點，而 k k k 因題而已，這個在下文 區間DP的進階 這一節里會講到，

2、狀態轉移

• 狀態轉移一定是從 區間長度短 的狀態 到 區間長度長 的狀態；

3、時間復雜度

• 涉及到利用 區間DP 來求解的問題，一般都有一個對應的序列：
• 1）當序列的長度為 n ≤ 300 n \le 300 n≤300 時，區間DP 的時間復雜度一般為 O ( n 3 ) O(n^3) O(n3)，其中 狀態轉移時間復雜度 為 O ( n ) O(n) O(n)；
• 2）當序列的長度為 n ≤ 1000 n \le 1000 n≤1000 時，區間DP 的時間復雜度一般為 O ( n 2 ) O(n^2) O(n2)，其中 狀態轉移時間復雜度 為 O ( 1 ) O(1) O(1)；

四、區間DP的求解

• 接下來我們再通過一道例題來完整了解下 區間DP 的求解程序，并且嘗試用 遞回 和 迭代 兩種方法來實作它，

【例題2】給定一個 n ( 3 ≤ n ≤ 100 ) n(3 \le n \le 100) n(3≤n≤100) 個元素的序列 a i a_i ai?，每洗掉一個元素，就會產生一定的消耗，消耗為它本身與相鄰兩數的乘積，首尾兩個數不能洗掉，問將數字洗掉到只剩兩個，最小的總消耗是多少，

1、思路分析

• 和石子歸并的思路一樣，如果采用暴力列舉洗掉的思路，利用深度優先搜索遍歷所有情況，得到的搜索樹，第一層有 n ? 2 n-2 n?2 種選擇，第二層有 n ? 3 n-3 n?3 種選擇，最后一層有一種選擇，整個演算法的時間復雜度為 O ( n ! ) O(n!) O(n!)，當 n = 5 n=5 n=5 的搜索樹如下圖所示（其中數字代表下標）：
  圖四-1-1
• 可以發現有很多重復的計算，比如 [125]、[135]、[145] 都被計算了兩次；
  圖四-1-2
• 搜索和動態規劃的區別就是動態規劃能夠把一些子問題計算出來以后存起來，下次要用到的時候直接回傳，無需重復計算，
• 對于一個序列，最后一定會經過 n ? 2 n-2 n?2 次洗掉數字變成只剩下首尾兩個數的情況，即：
  

• 那么根據 “正難則反” 的思想，我們不去考慮第一個洗掉的數，而是考慮最后一個被洗掉的數的情況；
• 令最后一個被洗掉的數是 a k a_k ak?，情況如下：
  圖四-1-4
• 也就是說，如果最后一個被洗掉的是 a k a_k ak?，那么消耗就是 a 1 a k a n a_1 a_k a_n a1?ak?an?，那么對于 [ 1... k ] [1 ... k] [1...k] 和 [ k . . . n ] [k ... n] [k...n] 這兩個區間，前者需要洗掉 k ? 2 k-2 k?2 個數，后者需要洗掉 n ? k ? 1 n-k-1 n?k?1 個數，并且兩個端點的數是不能被洗掉的，
• 這樣就把原本大區間的問題，轉換成了兩個小區間的問題，
• 令 f [ i ] [ j ] f[i][j] f[i][j] 表示區間 [ i , j ] [i, j] [i,j] 中的數洗掉除端點外的所有數得到的最小消耗，則有狀態轉移方程如下：
• f [ i ] [ j ] = { 0 j ? i ≤ 1 min ? k = i + 1 j ? 1 ( f [ i ] [ k ] + f [ k ] [ j ] + a i a k a j ) j ? i > 1 f[i][j] = \begin{cases}0 & j-i \le 1\\ \min_{k=i+1}^{j-1}(f[i][k] + f[k][j] + a_i a_k a_j) & j-i \gt 1\end{cases} f[i][j]={0mink=i+1j?1?(f[i][k]+f[k][j]+ai?ak?aj?)?j?i≤1j?i>1?
• f [ 1 ] [ n ] f[1][n] f[1][n] 即為最后的答案，

2、代碼實作

1）遞回實作

• 比較直觀的求解 區間DP 的方法是記憶化搜索，只要想好遞回出口 和 狀態轉移，基本就是套模板了，

int dfs(int l, int r) {
    if(l + 1 == r) {
        return 0;            // 1)
    }
    int &val = f[l][r];
    if(val != inf) {         // 2)
        return val;
    }
    val = 1e9;
    for(int k = l + 1; k < r; ++k) {
        int v = dfs(l, k) + dfs(k, r) + a[l] * a[k] * a[r];
        val = min(val, v);  // 3)
    } 
    return val;
}

• 1）當區間長度為 2 的時候，無需進行洗掉，已經到達遞回出口，所以消耗為 0；
• 2）初始化所有區間狀態值為 f [ l ] [ r ] = i n f f[l][r] = inf f[l][r]=inf，如果不等于這個值，說明已經計算出來了，則無需遞回計算，直接回傳已經計算出來的值即可；
• 3）利用子區間計算出來的值，進行狀態轉移；
• 關于記憶化搜索相關的內容，如果還有疑問，可以參考我之前寫的一篇文章：

2）迭代實作

• 當然也有迭代的方式來實作的，迭代求解需要注意狀態轉移的方向，之前已經說過，狀態轉移一定是從小區間往大區間進行轉移的，所以小區間的最優值需要先被計算出來，
• 于是我們可以按照區間的長度進行列舉，對于二維的狀態，前兩層列舉分別為 區間長度 和 區間左端點，我們來看看迭代版本的實作，

for (int len = 1; len <= n; ++len) {
    for (int l = 1; l + len - 1 <= n; ++l) {
        int r = l + len - 1;            // 1)
        if (len == 1 || len == 2) {
            f[l][r] = 0;                // 2)
            continue;
        }
        f[l][r] = 1e9;
        for (int k = l + 1; k < r; ++k) {
            int v = f[l][k] + f[k][r] + a[l] * a[k] * a[r];
            f[l][r] = min(f[l][r], v); // 3)
        }
    }
}

• 1）優先列舉區間長度 l e n len len，再列舉左端點 l l l，這樣區間右端點就可以通過兩者計算出來： r = l + l e n ? 1 r = l + len - 1 r=l+len?1，并且保證了狀態轉移的方向一定是從小區間到大區間；
• 2）這一步對應的是遞回實作的遞回出口部分；
• 3）這一步對應的是狀態轉移的部分；
• 如圖四-2-1的動圖，展示的是迭代求解的順序，灰色的格子代表無效狀態，紅色的格子代表為長度為 2 的區間，橙色的格子代表為長度為 3 的區間，金黃色的格子則代表長度為 4 的區間，黃色的格子代表我們最終要求的區間狀態，即 f [ 1 ] [ 5 ] f[1][5] f[1][5]，
  圖四-2-1

五、區間DP的進階

1、環形區間

【例題3】有 n ( n ≤ 100 ) n(n \le 100) n(n≤100) 堆石子擺放成一圈，第 i i i 堆的重量為 w i w_i wi?，現要將石子有次序地合并成一堆，規定每次只能選相鄰的二堆合并成新的一堆，合并的消耗為當前合并石子的總重量，試設計出一個演算法，計算出將 n n n 堆石子合并成一堆的最小消耗，

• 這個問題和 【例題1】 的區別在于原本的鏈狀結構變成了環狀結構，我們可以將石子拷貝一份同樣的資料，即令 w n + i = w i w_{n+i} = w_i wn+i?=wi?，將原來的長度為 n n n 的序列變成 2 n 2n 2n，然后列舉左端點 l ∈ [ 1 , n ] l \in [1,n] l∈[1,n]，做 n n n 次區間 DP，然后再取最小值，時間復雜度 O ( n 4 ) O(n^4) O(n4)，
• 注意到這里計算 [ l , l + n ] [l, l+n] [l,l+n] 和 [ l + 1 , l + 1 + n ] [l+1, l+1+n] [l+1,l+1+n] 區間DP 的最優值時， [ l + 1 , l + n ] [l+1, l+n] [l+1,l+n] 這段區間是兩者的重疊區間，所以這里同樣是可以記憶化的，即可以把 n n n 次 區間DP 放在一起做（即只需要一次初始化），然后求：
• min ? ( f [ 1 ] [ n ] , f [ 2 ] [ 1 + n ] , . . . , f [ n ] [ 2 n ? 1 ] ) \min( f[1][n], f[2][1+n], ..., f[n][2n-1]) min(f[1][n],f[2][1+n],...,f[n][2n?1])
• 就是最后的答案了，這時候，時間復雜度是 O ( n 3 ) O(n^3) O(n3) 的，

2、回文子序列

【例題4】給定一個 n ( n ≤ 1000 ) n( n \le 1000) n(n≤1000) 個元素 a i a_i ai? 的序列，求它的最長的回文子序列的長度，

• 令 f [ i ] [ j ] f[i][j] f[i][j] 為第 i i i 個元素到第 j j j 個元素的最長回文子序列的長度，考慮以下幾個情況：
• 1） i > j i \gt j i>j：這個時候代表它是個空串，所以最長回文子序列的長度肯定為 0；
• 2） i = j i=j i=j：對于長度為 1 的串，本身就是一個回文序列，所以最長回文子序列的長度為 1；
• 3） i < j ， a i ≠ a j i < j，a_i \neq a_j i<j，ai??=aj?：由于區間端點的兩個元素值不相等，所以 f [ i ] [ j ] f[i][j] f[i][j] 不可能比 f [ i + 1 ] [ j ] f[i+1][j] f[i+1][j] 或者 f [ i ] [ j ? 1 ] f[i][j-1] f[i][j?1] 更長，至多和兩者的大者相等，即 f [ i ] [ j ] = max ? ( f [ i + 1 ] [ j ] , f [ i ] [ j ? 1 ] ) f[i][j] = \max(f[i+1][j], f[i][j-1]) f[i][j]=max(f[i+1][j],f[i][j?1])，這樣就把區間縮小了；
• 4） i < j ， a i = a j i < j，a_i = a_j i<j，ai?=aj?：由于區間端點的兩個元素值相等，所以只需要知道這兩個元素包圍的區間的最大值，即 f [ i + 1 ] [ j ? 1 ] f[i+1][j-1] f[i+1][j?1]，再加上 2 就是包含兩端點的最長回文子序列的長度；那么當然還要考慮不包含的情況，也就是（3）的情況；
• 于是，可以得出狀態轉移方程如下：
• f [ i ] [ j ] = { 0 i > j 1 i = j max ? ( f [ i + 1 ] [ j ] , f [ i ] [ j ? 1 ] ) i < j , a i ≠ a j max ? { f [ i + 1 ] [ j ? 1 ] + 2 f [ i + 1 ] [ j ] f [ i ] [ j ? 1 ] i < j , a i = a j f[i][j] = \begin{cases}0 & i > j \\ 1 & i=j \\ \max(f[i+1][j], f[i][j-1]) & i < j, a_i \neq a_j \\ \max \begin{cases} f[i+1][j-1] + 2 \\ f[i+1][j] \\ f[i][j-1] \end{cases} & i < j, a_i = a_j\end{cases} f[i][j]=????????????????????01max(f[i+1][j],f[i][j?1])max??????f[i+1][j?1]+2f[i+1][j]f[i][j?1]??i>ji=ji<j,ai??=aj?i<j,ai?=aj??

3、輔助維

• 當單純區間無法表示狀態時，我們就需要增加輔助維來解決這個問題，下面的這道例題較難，屬于競賽難度，如果單純是為了面試而學的演算法，可以略過此題，

【例題5】（較難） n ( n ≤ 200 ) n ( n \le 200 ) n(n≤200) 個方塊排成一排，每個方塊一種顏色，每次可以選擇其中一種連續的顏色塊進行消除，消除的分數為色塊長度的平方，求最后全部色塊消除的總分，要求這個最大值；

如上圖所示，輸入：
9
1 2 2 2 2 3 3 3 1
輸出： 29 ( 4 2 + 3 2 + 2 2 ) 29 (4^2+3^2+2^2) 29(42+32+22)

• 首先對于這個問題，本身已經連在一起的方塊一定是一起消除的，所以首先一定要預處理輸入，將相同顏色的方塊歸并， c o l o r i color_i colori? 表示第 i i i 種方塊的顏色， n u m i num_i numi? 表示第 i i i 種方塊的數量；
• 那么如果用 f [ i ] [ j ] f[i][j] f[i][j] 來表示區間 [ i , j ] [i, j] [i,j] 下能夠消除得到的最大分數，我們發現無法進行狀態轉移，因為如果 i i i 和 j j j 能夠放在一起消除的條件是 [ i + 1 , j ? 1 ] [i+1, j-1] [i+1,j?1] 的區間上都已經被消除，但是從這個狀態表示上并不能體現，所以，我們需要增加一維來表示狀態，
• 令 f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k] 表示 [ i , j ] [i, j] [i,j] 消除，并且第 j j j 個塊連同后面 k k k 個顏色相同塊消去的最大分數；
• 1）第 j j j 個塊單獨和后面的 k k k 個塊消掉，那么分數為 f [ i ] [ j ? 1 ] [ 0 ] + ( n u m j + k ) 2 f[i][j-1][0] + (num_j+k)^2 f[i][j?1][0]+(numj?+k)2 ；
• 2）對于 s ∈ [ i , j ) s \in [i, j) s∈[i,j)，如果 c o l o r s = c o l o r j color_s = color_j colors?=colorj?，那么如果我們要把他們在后續歸并到一起，勢必中間的 ( s , j ) (s, j) (s,j) 這些塊要單獨計算，其最大值為 f [ s + 1 ] [ j ? 1 ] [ 0 ] f[s+1][j-1][0] f[s+1][j?1][0]；并且，為 [ i , s ] [i,s] [i,s] 這個區間的最后一種型別的塊，增加了 n u m j num_j numj? 個，即最大值為 f [ i ] [ s ] [ n u m j + k ] f[i][s][ num_j+k ] f[i][s][numj?+k]，則有:
• f [ i ] [ s ] [ n u m j + k ] + f [ s + 1 ] [ j ? 1 ] [ 0 ] f[i][s][ num_j + k ] + f[s+1][j-1][0] f[i][s][numj?+k]+f[s+1][j?1][0]
• 聯合（1） 和 （2）得出狀態轉移方程：
• f [ i ] [ j ] = max ? { f [ i ] [ j ? 1 ] [ 0 ] + ( n u m j + k ) 2 f [ i ] [ s ] [ n u m j + k ] + f [ s + 1 ] [ j ? 1 ] [ 0 ] c o l o r s = c o l o r j f[i][j] = \max \begin{cases} f[i][j-1][0] + (num_j+k)^2 \\ f[i][s][ num_j + k ] + f[s+1][j-1][0] & color_s = color_j\end{cases} f[i][j]=max{f[i][j?1][0]+(numj?+k)2f[i][s][numj?+k]+f[s+1][j?1][0]?colors?=colorj??

六、區間DP的常規思路

1、切割 / 合并區間

• 將大區間無腦切割成兩個子區間，分別計算兩個子區間的最優值，再通過兩個子區間的最優值，計算整個大區間的最優值，

2、last 原則

• 永遠不去想第一步要干什么，而是想最后一步是要干什么，然后再去列舉最后一步的所有情況，從而縮小區間，

3、添加輔助維

• 有時候二維的區間無法表示狀態，或者無法進行狀態轉移的時候，我們可以嘗試再增加一個緯度，然后再去想狀態轉移方程，

• 關于 區間 DP 的內容到這里就全部結束了，如果還有不懂的問題可以留言告訴作者或者添加作者的微信公眾號，

• 本文所有示例代碼均可在以下 github 上找到：github.com/WhereIsHeroFrom/Code_Templates

七、區間DP相關題集整理