Interval Dynamic Programming: In-Depth Analysis and Implementation of the Stone Merging Problem

Core Logic and Mathematical Principles

Interval Dynamic Programming (Interval DP) is a standard model for studying local interval merging and evolution on linear sequences. Its essence lies in using the interval length (Scale) as a stage for topological advancement. After the state of small intervals is completely solidified, the state can be contributed to larger intervals by enumerating the cut points within the intervals.

Stone Merging is a textbook model of Interval DP. Given a row of $N$ piles of stones, only adjacent piles can be merged at a time, and the cost of merging is the sum of the weights of the two piles. The goal is to find the minimum or maximum total cost to merge all stones into one pile.

The mathematical validity of Interval DP is supported by the following underlying logic:

1. Non-linear Division of Stages: Traditional linear DP advances sequentially from index $i = 1$ to $N$. However, in Interval DP, the "stages" are defined by the length of the interval $len$. Only when all sub-intervals of length $len-1$ have been fully computed and solidified can the computation for intervals of length $len$ commence.
2. Cut Point Mapping: For any closed interval $[l, r]$, the last step of merging it into one pile must come from merging two smaller adjacent sub-intervals $[l, k]$ and $[k+1, r]$. By enumerating cut points $k \\in [l, r-1]$, all possible last-step decisions can be explored.
3. Additivity of Interval Properties (Prefix Sum Optimization): The direct cost incurred when merging interval $[l, r]$ is precisely the sum of the weights of all original elements within that interval. To avoid the $O(N)$ overhead of naively summing the interval weights, a prefix sum array $S$ must be introduced to output the interval weight sum in $O(1)$ time: $W(l, r) = S[r] - S[l-1]$.

State Design and Algorithm Derivation

1. State Space Definition

Let the state $f[l][r]$ represent the minimum cost to merge all stones in the interval $[l, r]$ into one pile.

2. Derivation of State Transition Equation

Any large interval $[l, r]$ is formed by merging two sub-intervals, and its total cost is equal to: the cost of merging the left interval + the cost of merging the right interval + the direct cost of this merge.

$$f[l][r] = \min_{l \le k < r} \{ f[l][k] + f[k+1][r] \} + W(l, r)$$

where $W(l, r) = \sum_{i=l}^{r} A[i] = S[r] - S[l-1]$.

3. Standard $O(N^3)$ Loop Format and Topological Order

To ensure that when calculating $f[l][r]$, the right-hand side values $f[l][k]$ and $f[k+1][r]$ are already optimal solutions, the physical nesting order of the three loops must be strictly controlled:

• Outer Loop: Enumerate the interval length $len$ (from 2 to $N$).
• Middle Loop: Enumerate the left endpoint $l$ and dynamically compute the right endpoint $r = l + len - 1$.
• Inner Loop: Enumerate the cut point $k$ (from $l$ to $r-1$).

C++ Standard Source Code (NOIP Style)

The following source code is a standard implementation of the stone merging problem (finding minimum and maximum costs) using Interval DP, strictly adhering to the Linux g++ -O2 compilation standards.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAXN = 305;
const int INF = 0x3f3f3f3f;

int a[MAXN];
int s[MAXN]; // Prefix sum array
int f_min[MAXN][MAXN];
int f_max[MAXN][MAXN];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i]; // Preprocess prefix sums, O(1) to get interval weight sum
    }

    // Initialize boundaries: the cost of merging an interval of length 1 is 0, others initialized to extreme values
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i == j) {
                f_min[i][j] = 0;
                f_max[i][j] = 0;
            } else {
                f_min[i][j] = INF;
                f_max[i][j] = -INF;
            }
        }
    }

    // Strictly follow the standard three-layer format for topological traversal in Interval DP
    // Fatal pitfall: the outer loop must be the interval length len!
    for (int len = 2; len <= n; ++len) { 
        for (int l = 1; l <= n - len + 1; ++l) {
            int r = l + len - 1;
            int score = s[r] - s[l - 1]; // Total weight of the current interval

            for (int k = l; k < r; ++k) {
                // State transition: derive large interval results from small interval results
                f_min[l][r] = min(f_min[l][r], f_min[l][k] + f_min[k + 1][r] + score);
                f_max[l][r] = max(f_max[l][r], f_max[l][k] + f_max[k + 1][r] + score);
            }
        }
    }

    cout << f_min[1][n] << "\n" << f_max[1][n] << "\n";

    return 0;
}

NOIP Practical Pitfall Guide

1. Incorrectly Using $l$ and $r$ as the First Two Loops

• Phenomenon: Writing a double loop structure like for (int l = 1; l <= n; ++l) for (int r = l; r <= n; ++r) leads to the inner loop enumerating $k$. This will cause the calculation of $f[l][r]$ to depend on the right sub-interval $f[k+1][r]$, which has not yet been computed (its value remains initialized as INF), thereby crippling the entire state transition logic.
• Avoidance Method: Interval DP must strictly adhere to the loop order of "length $ o$ left endpoint $ o$ decision point" or "left endpoint (in reverse) $ o$ right endpoint $ o$ decision point". Remember that only when all short intervals are solidified can longer intervals be evaluated.

2. Ignoring Initialization of Length 1 Interval Values

• Phenomenon: Failing to explicitly initialize $f[i][i]$ to 0, or after performing memset(f_min, 0x3f, sizeof(f_min)), forgetting to restore $f[i][i] = 0$. This can lead to the calculation of the length 2 interval $f[l][l+1] = f[l][l] + f[l+1][l+1] + W$ directly adding two INFs, resulting in the final output being a pseudo maximum value.
• Avoidance Method: After completing the state initialization, visually confirm that the base state values (i.e., leaf nodes of length 1) are physically realistic (merging oneself incurs no cost, thus it must be 0).

Classic NOIP/Luogu Problems

1. Luogu P1775 Stone Merging (Weakened Version)

• Problem Description: Given $N$ piles of stones arranged in a row, numbered $1, 2, 3, \dots, N$. Each pile of stones has a certain mass. The task is to merge these $N$ piles into one pile. Each time, only adjacent piles can be merged, and the cost of merging is the sum of the masses of the two piles. Find the minimum total cost.
• Problem Essence and Solution Idea: A standard interval dynamic programming model, which is the minimum cost version derived above.
• Core Idea: Directly apply the standard $O(N^3)$ loop template. Use prefix sums for interval value summation optimization. Since this weakened version has $N \le 300$, the total computation in three nested loops is around $2.7 \times 10^7$, which takes less than 0.05 seconds in a Linux environment, easily passing the test.

2. Luogu P3143 [USACO16OPEN] Diamond Collector S

• Problem Description: Given $N$ positive integers, the task is to select two groups of numbers such that the difference between the maximum and minimum values within each group does not exceed $K$. The two groups cannot have overlapping elements (i.e., each position can be selected at most once). Find the maximum number of digits that can be included in both groups.
• Problem Essence and Solution Idea: A linear interval maximum value coverage and non-overlapping dual interval combination problem.
• Core Idea: First, sort the original array in ascending order so that elements with similar values are contiguous in space. Then, using the two-pointer (sliding window) technique, preprocess the farthest right endpoint satisfying the difference $\\le K$ for each left endpoint $i$, thereby obtaining the length of each valid local interval.
• Interval DP Dimensional Reduction Fusion: Let $L[i]$ represent the maximum number of elements that can be selected from a single group within the interval $[1, i]$, and $R[i]$ represent the maximum number of elements that can be selected from a single group within the interval $[i, N]$. They can be obtained through a one-way linear scan (essentially a recursive update of the interval maximum value). Finally, by enumerating the cut point $i$, the global maximum number is $\\max_{1 \le i < N} \{ L[i] + R[i+1] \}$. This avoids the $O(N^2)$ complexity caused by naively enumerating the dual intervals.