State Transition Equation

The foundational equation for this optimization is:

f(l, r) = min{f(l, k) + f(k + 1, r)} + w(l, r), where l ≤ k < r

Problem Context

Consider the classic stone merging problem where N piles of stones (N ≤ 300) are arranged linearly. Each pile has a weight mi (mi ≤ 1000). Adjacent piles can be merged with a cost equal to their combined weight. The objective is to determine the minimum total cost to merge all piles into one.

Define f(i, j) as the minimal cost to merge piles from index i to j, and w(i, j) as the sum of weights from pile i to j. The recurrence relation becomes:

f(i, i) = 0, for 0 ≤ i < N
f(i, j) = min{f(i, k) + f(k + 1, j)} + w(i, j), for i ≤ k < j

A standard implementation requires O(n³) time complexity:

vector<vector<int>> dp(n, vector<int>(n, INT_MAX));

// Base case
for (int i = 0; i < n; ++i) {
    dp[i][i] = 0;
}

// Fill table
for (int length = 1; length < n; ++length) {
    for (int left = 0; left < n - length; ++left) {
        int right = left + length;
        for (int split = left; split < right; ++split) {
            if (dp[left][split] + dp[split + 1][right] + weight[left][right] < dp[left][right]) {
                dp[left][right] = dp[left][split] + dp[split + 1][right] + weight[left][right];
            }
        }
    }
}

Under specific conditions, this can be optimized to O(n²).

Quadrangle Inequality Principal

Given weight function w(l, r), if for all l₁ ≤ l₂ ≤ r₁ ≤ r₂:

1. Interval Monotonicity: w(l₂, r₁) ≤ w(l₁, r₂)
2. Quadrangle Inequality: w(l₁, r₁) + w(l₂, r₂) ≤ w(l₁, r₂) + w(l₂, r₁)

Then the optimal solution f(l, r) also satisfies the quadrangle inequality:

f(l₁, r₁) + f(l₂, r₂) ≤ f(l₁, r₂) + f(l₂, r₁)

Mathematical Proof Structure

Case 1: Boundary Conditions

When l₁ = l₂ or r₁ = r₂, the inequality holds trivially.

Case 2: Overlapping Intervals

For l₁ < l₂ = r₁ < r₂, let u and v represent optimal decision points for f(l₁, r₂) and f(l₂, r₁) respectively:

(a) When u < r₁: Using mathematical induction on smaller subproblems, we establish: f(l₁, r₁) + f(l₂, r₂) ≤ f(l₁, u) + f(u + 1, r₁) + w(l₁, r₁) + f(l₂, r₂) ≤ f(l₁, u) + f(u + 1, r₂) + w(l₁, r₂) + f(l₂, r₁) = f(l₁, r₂) + f(l₂, r₁)

(b) When u ≥ r₁: Similarly: f(l₁, r₁) + f(l₂, r₂) ≤ f(l₁, r₁) + f(l₂, u) + f(u + 1, r₂) + w(l₂, r₂) ≤ f(l₁, u) + f(l₂, r₁) + f(u + 1, r₂) + w(l₁, r₂) = f(l₁, r₂) + f(l₂, r₁)

Case 3: Nested Intervals

For l₁ < l₂ < r₁ < r₂ with decision points u and v:

(a) When u ≤ v: The proof combines interval monotonicity with inductive reasoning on subproblem structures.

(b) When u > v: Symmetric argument applies using reverse ordering constraints.

Decision Point Monotonicity

When f(l, r) satisfies quadrangle inequality, the optimal decision points exhibit monotonic behavior:

m(l, r - 1) ≤ m(l, r) ≤ m(l + 1, r)

Where m(l, r) denotes the smallest optimal split point for interval [l, r].

Verification Approach

Let k₁ = m(l, r - 1), k = m(l, r), and k₂ = m(l + 1, r). To prove k₁ ≤ k ≤ k₂:

1. Contradiction for k < k₁: If k were smaller than k₁, it would yield a better solution than the assumed optimal k₁, violating optimality definition.

2. Contradiction for k > k₂: Similarly, k₂ would become a superior choice over k, contradicting k's optimality.

Therefore, optimal decision points must follow the established ordering.