Minimize Adjacent Merge Cost

Practice Exercise Intermediate Medium Interval DP Array

Checking your account…

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement minimum_adjacent_merge_cost(weights). Repeatedly merge two adjacent groups; merging costs the sum of their weights. Return the minimum total cost to merge all weights into one group. Empty or single input costs 0.

Starter code

def minimum_adjacent_merge_cost(weights):
    pass

Test cases

three-groups

{
  "args": [
    [
      3,
      2,
      4
    ]
  ]
}

Expected: 14

four-groups

{
  "args": [
    [
      2,
      2,
      1,
      2
    ]
  ]
}

Expected: 14

Wizard outline

Step 1: Seed singleton intervals
Create zero-cost bases and prefix sums. A single group needs no merge, and prefix sums make each future interval weight constant-time.
Step 2: Grow intervals by length
Fill every interval after its shorter dependencies. Every final split divides an interval into two already solved smaller intervals.
Step 3: Choose the global split optimum
Complete the full range and all intermediate interval choices. The optimal final merge must use one split, and optimal substructure lets each side use its own minimum.

Footguns and prerequisites

Adding each child sum instead of the full interval sum double-counts.
Filling long intervals before short dependencies leaves unknown child states.
dynamic programming

Reviewed references

Python Compound Statements — Function Definitions

Recommended approach and implementation

Tabulate minimum costs for increasing interval lengths and try every possible final split.

Why it works: Every full merge of an interval has one final split into two adjacent subintervals. The recurrence chooses the best solved cost for both sides plus the unavoidable final interval sum, covering all legal merge trees.

def minimum_adjacent_merge_cost(weights):
    n = len(weights)
    if n < 2:
        return 0
    prefix = [0]
    for weight in weights:
        prefix.append(prefix[-1] + weight)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        for left in range(n - length + 1):
            right = left + length - 1
            interval_sum = prefix[right + 1] - prefix[left]
            dp[left][right] = min(dp[left][split] + dp[split + 1][right] + interval_sum for split in range(left, right))
    return dp[0][n - 1]