Introduction

Consider a problem where N piles of stones are arranged in a line, each with a certain weight. The task is to merge these N piles into a single pile, with the constraint that only adjacent piles can be merged at each step, and the cost of each merge equals the combined weight of the two piles being merged. The objective is to find the minimum total cost of merging all stones into one pile.

A naive greedy approach fails here because local optimal decisions do not lead to global optimality. This is precisely the scenario where interval dynamic programming excels.

Definition

Interval DP extends linear DP by considering problems where element ordering and the composition of merged groups significantly impact the solution. The key concept involves partitioning intervals and combining optimal solutions from sub-intervals.

Let dp[i][j] represent the minimum (or maximum) value achievable by merging all elements from index i to index j. The state transition follows:

dp[i][j] = min/max { dp[i][k] + dp[k+1][j] + cost }

where cost represents the value or代价 incurred when combining the two resulting groups.

Key Properties

Interval DP exhibits these defining characteristics:

• Merging Operation: Combines two or more parts into a unified whole (this operation is reversible)
• Decomposition Feature: The problem must be decomposable into sub-problems that can be merged pairwise
• Optimal Substructure: The optimal solution for the entire interval can be constructed from optimal solutions of its sub-intervals

Core Approach

To solve for the optimal value of a large interval, one must first establish:

1. Optimal values for smaller intervals
2. Base case boundaries
3. A proper state transition equation

The solution builds upward from smaller intervals to larger ones.

Template Implementation

#include <bits/stdc++.h>
using namespace std;

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

int dp[MAXN][MAXN];
int prefix[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    if (!(cin >> n)) return 0;
    
    for (int i = 1; i <= n; i++) {
        cin >> prefix[i];
        prefix[i] += prefix[i-1];
        dp[i][i] = 0;
    }
    
    for (int length = 2; length <= n; length++) {
        for (int left = 1; left + length - 1 <= n; left++) {
            int right = left + length - 1;
            dp[left][right] = INF;
            
            for (int split = left; split < right; split++) {
                int mergeCost = prefix[right] - prefix[left - 1];
                dp[left][right] = min(dp[left][right], 
                    dp[left][split] + dp[split + 1][right] + mergeCost);
            }
        }
    }
    
    cout << dp[1][n] << "\n";
    return 0;
}

The outer loop iterates through interval lengths, the middle loop fixes the left boundary, and the inner loop tests all possible split points.

Worked Examples

Linear Interval: Symmetric Mountains

Problem: Given N mountains with heights h[i], find the minimum asymmetry for all contiguous substrings of length len (where 0 < len < N). Asymmetry is defined as the sum of absolute differences between symmetrically positioned mountains.

Brute Force Approach: Computing asymmetry for each interval independently results in O(n³) complexity, leading to time limit exceeded.

Optimized Solution: The asymmetry of a longer interval equals the asymmetry of its inner interval plus the contribution from the two boundary mountains.

#include <bits/stdc++.h>
using namespace std;

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

int heights[MAXN];
int asym[MAXN][MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    for (int i = 1; i <= n; i++) {
        cin >> heights[i];
    }
    
    for (int len = 1; len <= n; len++) {
        int best = INF;
        for (int left = 1; left + len - 1 <= n; left++) {
            int right = left + len - 1;
            asym[left][right] = asym[left + 1][right - 1] 
                               + abs(heights[left] - heights[right]);
            best = min(best, asym[left][right]);
        }
        cout << best << " ";
    }
    
    return 0;
}

The recurrence asym[l][r] = asym[l+1][r-1] + |h[l] - h[r]| elegantly captures the recursive nature of asymmetry.

Stone Merging (Linear Version)

Problem: Merge N piles of stones arranged in a line, where only adjacent piles can be merged, and merge cost equals the combined weight. Find the minimum total cost.

The solution leverages prefix sums for efficient range cost calculation:

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;
const int INFINITY = 0x3f3f3f3f;

int f[305][305];
int acc[10005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    memset(f, 0x3f, sizeof(f));
    
    for (int i = 1; i <= n; i++) {
        int w;
        cin >> w;
        acc[i] = acc[i - 1] + w;
        f[i][i] = 0;
    }
    
    for (int span = 2; span <= n; span++) {
        for (int l = 1; l + span - 1 <= n; l++) {
            int r = l + span - 1;
            for (int mid = l; mid < r; mid++) {
                int combineCost = acc[r] - acc[l - 1];
                f[l][r] = min(f[l][r], f[l][mid] + f[mid + 1][r] + combineCost);
            }
        }
    }
    
    cout << f[1][n] << "\n";
    return 0;
}

Complexity Analysis: The naive approach runs in O(n³) time. For larger inputs, optimization techniques such as the Knuth optimizaton or monotonic queue optimization may be necessary.

Circular Stone Merging

Problem: Identical to the linear version, but the N piles are arranged in a circle.

Transformation Strategy: Duplicate the array to simulate the circular nature, then solve the linear problem on all possible starting points.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;
const int INFINITY = 0x3f3f3f3f;

int g[605][605];
int sum[10005];
int val[10005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    memset(g, 0x3f, sizeof(g));
    
    for (int i = 1; i <= n; i++) {
        cin >> val[i];
        val[i + n] = val[i];
        g[i][i] = g[i + n][i + n] = 0;
    }
    
    for (int i = 1; i <= 2 * n; i++) {
        sum[i] = sum[i - 1] + val[i];
    }
    
    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= 2 * n; l++) {
            int r = l + len - 1;
            for (int mid = l; mid < r; mid++) {
                int mergeCost = sum[r] - sum[l - 1];
                g[l][r] = min(g[l][r], 
                    g[l][mid] + g[mid + 1][r] + mergeCost);
            }
        }
    }
    
    int answer = INFINITY;
    for (int i = 1; i <= n; i++) {
        answer = min(answer, g[i][i + n - 1]);
    }
    
    cout << answer << "\n";
    return 0;
}

By considering all length-n intervals within the duplicated array, we capture all possible circular configurations.

Palindrome Insertion

Problem (IOI2000): Given a string, insert the minimum number of characters to make it a palindrome.

State Transition: For interval [l, r]:

1. If s[l] == s[r]: No insertion needed for these boundaries → dp[l][r] = dp[l+1][r-1]
2. If s[l] != s[r]: Must insert at one end → dp[l][r] = min(dp[l+1][r], dp[l][r-1]) + 1

#include <bits/stdc++.h>
using namespace std;

const int MAXM = 1005;

int dp[MAXM][MAXM];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string s;
    cin >> s;
    int m = s.length();
    
    for (int len = 2; len <= m; len++) {
        for (int l = 1; l + len - 1 <= m; l++) {
            int r = l + len - 1;
            if (s[l - 1] == s[r - 1]) {
                dp[l][r] = dp[l + 1][r - 1];
            } else {
                dp[l][r] = min(dp[l + 1][r], dp[l][r - 1]) + 1;
            }
        }
    }
    
    cout << dp[1][m] << "\n";
    return 0;
}

Practice Problems