跳转至

區間 DP

定義

區間類動態規劃是線性動態規劃的擴展，它在分階段地劃分問題時，與階段中元素出現的順序和由前一階段的哪些元素合併而來有很大的關係。

令狀態 \(f(i,j)\) 表示將下標位置 \(i\) 到 \(j\) 的所有元素合併能獲得的價值的最大值，那麼 \(f(i,j)=\max\{f(i,k)+f(k+1,j)+cost\}\)，\(cost\) 為將這兩組元素合併起來的價值。

性質

區間 DP 有以下特點：

合併：即將兩個或多個部分進行整合，當然也可以反過來；

特徵：能將問題分解為能兩兩合併的形式；

求解：對整個問題設最優值，枚舉合併點，將問題分解為左右兩個部分，最後合併兩個部分的最優值得到原問題的最優值。

解釋

例題

「NOI1995」石子合併

題目大意：在一個環上有 \(n\) 個數 \(a_1,a_2,\dots,a_n\)，進行 \(n-1\) 次合併操作，每次操作將相鄰的兩堆合併成一堆，能獲得新的一堆中的石子數量的和的得分。你需要最大化你的得分。

需要考慮不在環上，而在一條鏈上的情況。

令 \(f(i,j)\) 表示將區間 \([i,j]\) 內的所有石子合併到一起的最大得分。

寫出 狀態轉移方程：\(f(i,j)=\max\{f(i,k)+f(k+1,j)+\sum_{t=i}^{j} a_t \}~(i\le k<j)\)

令 \(sum_i\) 表示 \(a\) 數組的前綴和，狀態轉移方程變形為 \(f(i,j)=\max\{f(i,k)+f(k+1,j)+sum_j-sum_{i-1} \}\)。

怎樣進行狀態轉移

由於計算 \(f(i,j)\) 的值時需要知道所有 \(f(i,k)\) 和 \(f(k+1,j)\) 的值，而這兩個中包含的元素的數量都小於 \(f(i,j)\)，所以我們以 \(len=j-i+1\) 作為 DP 的階段。首先從小到大枚舉 \(len\)，然後枚舉 \(i\) 的值，根據 \(len\) 和 \(i\) 用公式計算出 \(j\) 的值，然後枚舉 \(k\)，時間複雜度為 \(O(n^3)\)

怎樣處理環

題目中石子圍成一個環，而不是一條鏈，怎麼辦呢？

方法一：由於石子圍成一個環，我們可以枚舉分開的位置，將這個環轉化成一個鏈，由於要枚舉 \(n\) 次，最終的時間複雜度為 \(O(n^4)\)。

方法二：我們將這條鏈延長兩倍，變成 \(2\times n\) 堆，其中第 \(i\) 堆與第 \(n+i\) 堆相同，用動態規劃求解後，取 \(f(1,n),f(2,n+1),\dots,f(n-1,2n-2)\) 中的最優值，即為最後的答案。時間複雜度 \(O(n^3)\)。

實現

1
2
3
4
5
6
for (len = 2; len <= n; len++)
  for (i = 1; i <= 2 * n - 1 - len; i++) {
    int j = len + i - 1;
    for (k = i; k < j; k++)
      f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j] + sum[j] - sum[i - 1]);
  }

1
2
3
4
5
for len in range(2, n + 1):
    for i in range(1, 2 * n - len):
        j = len + i - 1
        for k in range(i, j):
            f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j] + sum[j] - sum[i - 1])

幾道練習題

NOIP 2006 能量項鍊

NOIP 2007 矩陣取數遊戲

「IOI2000」郵局

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用