555. The Cheapest Merge of Adjacent Piles
Piles of stones sit in a row. Merging two ADJACENT piles costs the total of the two piles, and produces a single pile of that size. Repeat until one pile remains.
Print the smallest total cost.
4 3 3 4 -> 28
1 2 -> 3 one merge, costing 1 + 2
## Why the cheapest pair first is wrong
Always merging the two cheapest adjacent piles is the natural greedy, and it fails because merging creates a pile that must be merged AGAIN later, so a cheap merge now can leave an expensive one to come.
That is the difference from the version where any two piles may be merged, not only adjacent ones. There, a priority queue and repeated cheapest-pair merging IS optimal, and that is problem #867. The adjacency restriction is what breaks it and forces a table.
The contrast is worth holding onto: the two problems differ by one word and by an entire technique.
## The state
Merging only adjacent piles means every intermediate pile is a CONTIGUOUS run of the originals. So a range is the right state:
dp[i][j] = the cheapest way to merge piles i..j into one
## The recurrence
The LAST merge combines two piles that between them cover the whole range, so it splits the
range at some k:
dp[i][j] = (sum of i..j) + min over k in i..j-1 of dp[i][k] + dp[k+1][j]
The sum term is the cost of that final merge, which is the total of the range no matter where the split is, because the two pieces together hold every stone in the range.
Pulling it outside the minimum makes that explicit: the split only affects what happened BEFORE the last merge.
## The prefix sum
The range total is needed for every (i, j), so precompute prefix sums. Summing inside the
loop adds a factor of n.
## Boundaries
A single pile answers 0: nothing needs merging. 1 answers 0, and a solution that always
charges at least one merge gets it wrong.
1 2 3 answers 9, which is small enough to check by hand: merge 1 and 2 for 3, then 3 and 3
for 6, giving 9. Merging 2 and 3 first gives 5 then 6, which is 11.
5 5 5 5 answers 40 and 6 4 4 6 answers 40 as well, which is worth noticing: the same
total with a different arrangement can give the same answer, so equal answers do not imply
equal structure.
## Cost
Time O(n^3). Space O(n^2).
## Where this appears again
This is the classic interval DP, and problem 562 is the same question when exactly k piles
must be merged at a time rather than two. The step from 2 to k adds a feasibility
condition and a stride to the split loop, and nothing else.
Constraints - `1 ≤ n ≤ 150` - `1 ≤ pile size ≤ 10000`
Input
The first line contains an integer n.
The second line contains n pile sizes.
Output
Print the smallest total cost of merging every pile into one.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.