All problems

Chain Snapping Effort

Hard · dynamic programming

A jeweller has a straight chain made of links in a row. The list weights gives the weight of each link, from left to right. The chain has to be taken apart completely by snapping links open, one at a time.

A snap works like this. You hold one piece of chain (a run of links that are still joined together) and choose one link in it. That link is snapped open and removed. The links to its left stay joined as one piece, the links to its right stay joined as another piece, and either of them may be empty.

The effort of a snap is the total weight of the whole piece you were holding, counted before the snap. You may start on any piece you like and work in any order, until no link is left.

Return the smallest possible total effort.

Examples

Example 1

Input: weights = [3, 1, 2]

Output: 10

Snap the link of weight 3 first (effort 6), then the link of weight 2 in the piece [1, 2] (effort 3), then the last link (effort 1). The total is 10, and no other order does better.

Example 2

Input: weights = [5]

Output: 5

A single link is snapped with an effort equal to its weight.

Example 3

Input: weights = [2, 2, 2, 2]

Output: 16

Snap the second link first (effort 8). That leaves [2] (effort 2) and [2, 2] (effort 4, then 2). The total is 8 + 2 + 4 + 2 = 16.

Constraints