Dynamic programming 0/50

Lesson 3 of 3 Advanced

Interval DP: combining contiguous subproblems

Solve a problem on every contiguous range, shortest first, by trying the final split or the move at either end.

5,450 words · 25 min read

Part 1 of 10 Slimes

Interval DP and the Slimes problem

Many of the states so far described a prefix of the input: the first ii stones, the first ii items, the first ii characters of a string. The longest palindromic subsequence was different, because its state named both ends of a range of the string. In interval DP, also called range DP, a state is a range of consecutive positions, and the range can start and end anywhere in the row. The first problem is Slimes.

Difficulty tier:Easy

NN slimes stand in a row, and the ii-th has size aia_i. One step picks two slimes that are next to each other and merges them into a single slime, which takes their place in the row. Its size is the sum of the two sizes, and the step costs that sum. The steps repeat until one slime is left. Print the smallest possible total cost.

The first input line holds NN and the second the sizes a1,…,aNa_1, \dots, a_N.

Constraints

  • 2≤N≤4002 \le N \le 400
  • 1≤ai≤1091 \le a_i \le 10^9

Sample 1 · Input

4
10 20 30 40

Output

190

Sample 2 · Input

5
10 10 10 10 10

Output

120

Sample 3 · Input

3
1000000000 1000000000 1000000000

Output

5000000000

Each merge turns two slimes into one, so NN slimes take N−1N - 1 merges. In the first sample we can merge from the left:

Each row is the result of one merge, and the highlighted slime is the new one. The total cost is 30+60+100=19030 + 60 + 100 = 190.

The order of the merges changes the total. Merging the same four slimes from the right costs 70+90+100=26070 + 90 + 100 = 260. There are three neighbouring pairs to choose from for the first merge, two for the second and one for the third, which makes 3×2×1=63 \times 2 \times 1 = 6 orders. Tried one by one, they cost 190, 200, 200, 210, 240 and 260, and the cheapest is the left-to-right order above.

A program could try every order and keep the cheapest, but there are too many of them. By the same counting, NN slimes have (N−1)!(N - 1)! orders, and for the 400 slimes the problem allows that number has 867 digits.

It is tempting to skip the search and choose each merge by a rule that looks only at the row as it stands, for example by always merging the neighbouring pair with the smallest sum. A rule like that never works out what a choice will cost in the later merges. It finds 190 on the first sample, but on the row 3, 2, 2, 3 it merges the two 2s first, and another order is cheaper:

the two 2s first:4+7+10=21each 3 with the 2 beside it:5+5+10=20\begin{aligned} \text{the two 2s first:}&\quad 4 + 7 + 10 = 21 \\ \text{each 3 with the 2 beside it:}&\quad 5 + 5 + 10 = 20 \end{aligned}

A merge costs the total size of the slime it makes, so the size of each original slime is paid once for every merge that contains it. Merging the two 2s is the cheapest first move, but it puts both 2s inside all three merges, and each of them is paid for three times. In the cheaper order every slime is inside exactly two merges. We need a method that compares all the orders without listing them.