Dynamic programming · HTML
dp[l][r] describes closed interval [l,r]. In increasing length order, dp[l][r]=Aggregate_k(Combine(dp[l][k],dp[k+1][r],local(l,k,r))) or an endpoint-removal recurrence.
Recognition signals
- A subproblem is uniquely described by contiguous endpoints l and r.
- The last action splits the interval into shorter intervals or removes an endpoint.
- Merge order, parenthesization, palindrome structure, or paired elimination affects value.
- The same subinterval recurs under many outer decisions.
- Both interval lengths and internal split points must be considered.
False friends
| Signal | Why it is different |
|---|
| Selecting independent external intervals | Endpoint greedy or weighted-interval DP is more direct when the intervals are input objects rather than subranges. |
| An arbitrary subset with holes | Two endpoints cannot represent removed interior choices; use a bitmask or richer state. |
| A merge with a proven greedy order | If an exchange rule applies, avoid an unnecessary O(n³) interval table. |
Core invariant
Before intervals of length len are processed, every shorter dependency is correct; dp[l][r] enumerates every legal final action for that interval.
State, transition, and processing order
| Item | Definition |
|---|
| State | An optimum/count for closed endpoints (l,r), optionally with split[l][r] for reconstruction. |
| Transition | Enumerate the final split k or endpoint pair/removal and combine shorter interval answers with local cost. |
| Frontier / order | Increasing interval length; within a length, choose l and set r=l+length-1. |
Python skeleton
def min_merge_cost(values):
n = len(values)
if n <= 1: return 0
prefix = [0]
for x in values: prefix.append(prefix[-1] + x)
dp = [[0] * n for _ in range(n)]
for length in range(2, n + 1):
for l in range(n - length + 1):
r = l + length - 1
total = prefix[r + 1] - prefix[l]
dp[l][r] = min(
dp[l][k] + dp[k + 1][r] + total
for k in range(l, r)
)
return dp[0][n - 1]
Correctness sketch
- Intervals of length zero or one require no merge, establishing the base.
- Every full merge structure has a unique final split k whose two children are shorter intervals.
- By induction both children are optimal; enumerating every k and taking the best neither misses a structure nor exceeds the true optimum.
Complexity
| Time | Space | Parameters |
|---|
| Typically O(n³), potentially O(n²) with proven transition optimization | O(n²) | n is sequence length; each of O(n²) intervals tests O(n) splits. |
Edge cases
- empty or singleton input
- closed endpoint conventions
- starting interval length
- prefix calculation of local cost
- unreachable sentinels
- multiple equally optimal splits
Error patterns
| Pattern | Why it fails / fix |
|---|
| Filling by raw l/r order | A large interval may read an unfinished short one; length order is the dependency topology. |
| Overlapping or missing split ranges | With left [l,k], right must be [k+1,r], for k from l through r-1. |
| Double-counting the local total | Specify whether a cost belongs to the final merge or was already included by children. |
| Claiming O(n²) too quickly | There are O(n²) intervals and ordinarily O(n) split candidates per interval. |
Selection and exclusion rules
- Describe the final operation that divides the interval.
- Use increasing length so all dependencies are shorter.
- Precompute prefix aggregates for O(1) interval costs.
- When O(n³) is too large, verify formal optimization conditions before applying them.
Original micro-example
| Part | Detail |
|---|
| Result | dp[0][2]=9, with the final split after the second pile. |
| Setup | Adjacent piles weigh [2,1,3]; merging two costs their combined weight. |
| Trace | Merge 2+1 for 3, then merge with 3 for 6, totaling 9; the other order costs 4+6=10. |
Recall prompts
My notes