Skip to content

Interval DP

Definition

Interval DP is an extension of linear dynamic programming. When dividing the problem into stages, it heavily depends on the order in which elements appear and which elements from the previous stage are merged.

Let state \(f(i,j)\) represent the maximum value obtainable by merging all elements from index position \(i\) to \(j\). Then \(f(i,j)=\max\{f(i,k)+f(k+1,j)+cost\}\), where \(cost\) is the value gained from merging these two groups of elements.

Characteristics

Interval DP has the following features:

Merging: Integrating two or more parts, which can also be reversed.

Characteristic: The problem can be decomposed into forms that can be merged pairwise.

Solution: Define the optimal value for the entire problem, enumerate the merge points, decompose the problem into left and right parts, and finally merge the optimal values of the two parts to obtain the optimal value for the original problem.

Explanation

Example

「NOI1995」Stone Merging

Problem Summary: There are \(n\) numbers \(a_1,a_2,\dots,a_n\) arranged in a circle. Perform \(n-1\) merge operations, each operation merging two adjacent piles into one pile, gaining a score equal to the sum of the stones in the new pile. You need to maximize your total score.

First, consider the case where the stones are arranged in a line instead of a circle.

Let \(f(i,j)\) represent the maximum score obtained by merging all stones in the interval \([i,j]\).

Write the state transition equation: \(f(i,j)=\max\{f(i,k)+f(k+1,j)+\sum_{t=i}^{j} a_t \}~(i\le k<j)\)

Let \(sum_i\) denote the prefix sum of array \(a\). The state transition equation becomes \(f(i,j)=\max\{f(i,k)+f(k+1,j)+sum_j-sum_{i-1} \}\).

How to Perform State Transitions

Since computing \(f(i,j)\) requires knowing the values of all \(f(i,k)\) and \(f(k+1,j)\), and both of these involve fewer elements than \(f(i,j)\), we use \(len=j-i+1\) as the DP stage. First, enumerate \(len\) from small to large, then enumerate \(i\), compute \(j\) using \(len\) and \(i\), and finally enumerate \(k\). The time complexity is \(O(n^3)\).

How to Handle the Circle

In the problem, the stones are arranged in a circle, not a line. How to handle this?

Method 1: Since the stones form a circle, we can enumerate the split position to convert the circle into a line. As this requires \(n\) enumerations, the final time complexity is \(O(n^4)\).

Method 2: Extend the line to twice its length, making \(2\times n\) piles, where the \(i\)-th pile is the same as the \((n+i)\)-th pile. After solving with dynamic programming, take the optimal value among \(f(1,n),f(2,n+1),\dots,f(n,2n-1)\) as the final answer. The time complexity is \(O(n^3)\).

Implementation

1
2
3
4
5
6
for (len = 2; len <= n; len++)
  for (i = 1; i <= 2 * n - 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 + 1):
        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])

Practice Problems

NOIP 2006 Energy Necklace

NOIP 2007 Matrix Number Game

「IOI2000」Post Office

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