Interval DP: try every split

Lesson · 9 min read · Dynamic programming · Pattern: interval DP

For a range [i, j], try every position k for the last (or first) operation, combine the two sides, and pay for joining them.

The pattern

Matrix chain multiplication is the model. The state is a range; the choice is a split point k inside it; the two sides are independent smaller ranges; and there is a cost for the step that joins them.

Interval DP

best(i, j)

= opt over k in the range of best(i, k) ⊕ best(k, j) ⊕ join(i, k, j).

order

by increasing length; best of an empty or single range is the base case.

The hard part is choosing what k means. For burst balloons it is the balloon burst LAST in the range, because then its neighbours at that moment are known: the range ends. Choosing "first" leaves the neighbours undetermined.

Worked example: burst balloons

Bursting balloon k earns nums[left] · nums[k] · nums[right] with its current neighbours. Pad with 1 at both ends; coins(i, j) for the open range between i and j = max over the last balloon k of coins(i, k) + coins(k, j) + v[i] · v[k] · v[j].

Balloons 3, 1, 5, 8 padded to 1, 3, 1, 5, 8, 1.

Step 1 / 4

from 0
0031·2·3·4
from 1
001152·3·4
from 2
0102403·4
from 3
01203404
from 4
012304
Ranges with 1 balloon inside: (0, 2): last 3, 3; (1, 3): last 1, 15; (2, 4): last 5, 40; (3, 5): last 8, 40.
Step 2 / 4

from 0
0031302·3·4
from 1
0011521353·4
from 2
0102403484
from 3
01203404
from 4
012304
Ranges with 2 balloons inside: (0, 3): last 3, 30; (1, 4): last 5, 135; (2, 5): last 8, 48.
Step 3 / 4

from 0
00313021593·4
from 1
00115213531594
from 2
0102403484
from 3
01203404
from 4
012304
Ranges with 3 balloons inside: (0, 4): last 3, 159; (1, 5): last 8, 159.
Step 4 / 4

from 0
003130215931674
from 1
00115213531594
from 2
0102403484
from 3
01203404
from 4
012304
Ranges with 4 balloons inside: (0, 5): last 8, 167. The answer is 167.

Problems

TimeO(n³)

SpaceO(n²)