AIOJ

Definition

Interval dynamic programming is an extension of linear dynamic programming. When the problem is divided into stages, it depends heavily on the order in which elements appear in a stage and on which elements from the preceding stage are merged to form it.

Let the state $f(i,j)$ denote the maximum value obtained by merging all elements from positions $i$ through $j$ . Then $f(i,j)=\max\{f(i,k)+f(k+1,j)+cost\}$ , where $cost$ is the value obtained by merging the two groups of elements.

Properties

Interval DP has the following characteristics:

Merging: combine two or more parts; the operation can of course also be viewed in reverse.

Structure: the problem can be decomposed into parts that can be merged pairwise.

Solution: define the optimum for the whole problem, enumerate the split point, divide the problem into left and right parts, and finally merge the two optimal values to obtain the optimum for the original problem.

Explanation

Examples

「NOI1995」Stone Merging

Problem statement: There are $n$ numbers $a_1,a_2,\dots,a_n$ arranged on a circle. Perform $n-1$ merge operations; each operation merges two adjacent piles into one and scores the sum of the stones in the newly formed pile. Maximize the total score.

First consider the case where the piles form a chain rather than a circle.

Let $f(i,j)$ be the maximum score for merging all stones in the interval $[i,j]$ .

The state transition is $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 the array $a$ . The transition can then be written as $f(i,j)=\max\{f(i,k)+f(k+1,j)+sum_j-sum_{i-1} \}$ .

Performing the State Transition

To compute $f(i,j)$ , we need all values of $f(i,k)$ and $f(k+1,j)$ . Both intervals contain fewer elements than $f(i,j)$ , so use $len=j-i+1$ as the DP stage. Enumerate $len$ in increasing order, then enumerate $i$ , calculate $j$ from $len$ and $i$ , and finally enumerate $k$ . The time complexity is $O(n^3)$ .

Handling the Circle

How should we handle the fact that the stones form a circle rather than a chain?

Method 1: Enumerate the position at which to cut the circle and turn it into a chain. Since there are $n$ possible cuts, the final time complexity is $O(n^4)$ .

Method 2: Extend the chain to twice its length, obtaining $2\times n$ piles, where pile $i$ is identical to pile $n+i$ . Solve it with dynamic programming, then take the optimum 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

C++

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]);
  }

Python

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 Game

「IOI2000」Post Office