Interval DP and the Slimes problem
Many of the states so far described a prefix of the input: the first stones, the first items, the first 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.
slimes stand in a row, and the -th has size . 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 and the second the sizes .
Constraints
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 slimes take merges. In the first sample we can merge from the left:
The order of the merges changes the total. Merging the same four slimes from the right costs . There are three neighbouring pairs to choose from for the first merge, two for the second and one for the third, which makes 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, slimes have 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:
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.
Build the transition from the last merge
Only neighbours merge, so a slime never holds slimes from two separate parts of the row. At any moment, every slime in the row is made of a run of consecutive slimes from the original row. After the two merges and , for example, the first sample looks like this:
So the smaller questions are about ranges. Number the slimes from 0, and let dp[l][r] be the smallest cost of merging slimes to , both ends included, into one slime. The answer to the problem is dp[0][N - 1].
To find the transition we look at the last step, as we did with the frog's last jump. The last merge inside the range from to joins two slimes. The left one is made of slimes to and the right one of slimes to , for some position from to . We call the split. An order whose last merge has this split pays for three things:
- Making the left slime. The cheapest way costs
dp[l][k]. - Making the right slime. The cheapest way costs
dp[k + 1][r]. - The last merge. The slime it makes holds every slime from to , so it costs the sum of their sizes, which we write . This cost is the same for every split.
The two sides do not affect each other. The merges that make the left slime touch only slimes to , and they change no cost on the right. So if an order made the left slime in a more expensive way, replacing those merges with the cheapest ones for slimes to would lower the order's total and leave the rest unchanged, and the same goes for the right side. Each split gives one candidate, and the transition keeps the smallest:
The base cases are the ranges of a single slime. Nothing has to be merged there, so dp[l][l] is 0.
Take the first three slimes of the sample, 10, 20 and 30. A range of two slimes has one split, and both of its sides are single slimes, so dp[0][1] is and dp[1][2] is . The range of all three has the total 60 and two splits:
The smaller candidate is 90, so dp[0][2] is 90, and the cheapest order for these three slimes merges 10 and 20 first.
Fill the ranges in order of length
A candidate for dp[l][r] reads dp[l][k] and dp[k + 1][r]. Both ranges lie inside the range from to and are shorter than it. So the evaluation order goes by length: every range of one slime first, then every range of two, and so on up to the whole row.
Here is the finished table for the first sample, with a row for each and a column for each :
dp[0][3].The ranges of one length lie on a diagonal of this table. The main diagonal holds the base cases. The next one holds the ranges of two slimes, 30, 50 and 70, which are the sums of the three neighbouring pairs. Then come the ranges of three: 90, which we computed above, and 140. The 140 is dp[1][3], for the slimes 20, 30 and 40. Their total is 90, and the two candidates are and .
Other evaluation orders work as well. In this table, a candidate for dp[l][r] reads dp[l][k], which lies in the same row to its left, and dp[k + 1][r], which lies in the same column below it. So any order that fills each entry after the entries to its left and below it is correct. The order by length fills the table one diagonal at a time. Filling the rows from the bottom up, each from left to right, also works, and so does filling the columns from left to right, each from the bottom up.
The last entry to be filled is dp[0][3], for the whole row. It has three candidates, and every entry they read is already in the table:
The smallest of 240, 200 and 190 is the expected output, 190.
The Slimes program
The transition needs for every range. Adding up the sizes of each range with a loop would work, but a prefix-sum array gives the total with one subtraction. If prefix[i] is the sum of the first sizes, the total of slimes to is prefix[r + 1] - prefix[l]. For the sample the prefix sums are 0, 10, 30, 60 and 100, and the total of slimes 1 to 3 is .
The program has three loops: over the length of the range, over its left end , and over the split .
def min_merge_cost(a):
n = len(a)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + a[i]
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
best = float("inf")
for k in range(l, r):
best = min(best, dp[l][k] + dp[k + 1][r])
dp[l][r] = best + prefix[r + 1] - prefix[l]
return dp[0][n - 1]
n = int(input())
a = list(map(int, input().split()))
print(min_merge_cost(a))On the first sample the program prints 190.
Python details
The minimum starts at float("inf"), which is larger than every number, so that the first candidate replaces it. With CPython 3.14 on a 2025 laptop this program took about half a second for 400 slimes, and the judge allows 2 seconds.
The right end has no loop of its own. Once the length and are chosen, is . The loop over lengths starts at 2 because the table is created full of zeros, which are already the right values for the ranges of one slime.
The table has about states with up to candidates each, so the time is and the space . Both bounds can be read off the transition before any code is written: a state is named by two indices, and , a candidate by three, , and , and each index takes up to values. Counted exactly, a range of length has candidates and the row has ranges of that length, which adds up to
candidates: 10,666,600 for .
Worked example
Predict each candidate yourself
The trace computes the table for 10, 20 and 30 one candidate at a time. Its labels differ from ours: it writes interval for a range, piles for the slimes and left for . Switch on Predict the next step to work out each value before the trace shows it. The other inputs are four equal slimes, a heavy slime in front of three light ones, and the row 3, 2, 2, 3, on which the cheapest-pair rule lost.
dp[left][right] is the cheapest cost to merge that inclusive interval. A single pile needs no merge, so the diagonal starts at 0.
- piles
- 10, 20, 30
Change the example input
Current result: 90
Deeper read: print the merges
The table gives the cheapest cost and not the merges that reach it. To get the merges we use parent links, which record the choice each entry kept. While the table is filled, a second table split stores, for each range, the split whose candidate it kept. The cheapest order for a range then makes the part up to its split in the cheapest way, makes the part after it in the cheapest way, and merges the two results. The function show writes that as text, with a pair of brackets around each merge.
def merge_order(a):
n = len(a)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + a[i]
dp = [[0] * n for _ in range(n)]
split = [[0] * n for _ in range(n)]
for length in range(2, n + 1):
for l in range(n - length + 1):
r = l + length - 1
best = float("inf")
for k in range(l, r):
if dp[l][k] + dp[k + 1][r] < best:
best = dp[l][k] + dp[k + 1][r]
split[l][r] = k
dp[l][r] = best + prefix[r + 1] - prefix[l]
def show(l, r):
if l == r:
return str(a[l])
k = split[l][r]
return "(" + show(l, k) + " " + show(k + 1, r) + ")"
return dp[0][n - 1], show(0, n - 1)
print(*merge_order([10, 20, 30, 40]))
print(*merge_order([3, 2, 2, 3]))Prints each cost followed by the merges that reach it.
For the first sample it prints 190 (((10 20) 30) 40), the cost and the left-to-right order. For 3, 2, 2, 3 it prints 20 ((3 2) (2 3)), the order that cost 20. When two splits give the same cost, the program keeps the one it met first.
Split a polygon at a shared vertex
In Slimes every split added the same cost, the total of the range. In the next problem the cost depends on where the split is.
A convex polygon has vertices, and values[i] is the value of vertex , with the vertices numbered in clockwise order. A triangulation cuts the polygon into triangles whose corners are vertices of the polygon. Each triangle scores the product of its three corner values, and the score of a triangulation is the sum over its triangles. Return the smallest possible score.
Constraints
-
values[i]
Sample 1 · Input
values = [1,2,3]
Output
6
Sample 2 · Input
values = [3,7,4,5]
Output
144
Sample 3 · Input
values = [1,3,1,4,1,5]
Output
13
The first sample is a single triangle, with score . The second has four vertices. We number the vertices from 0 in the order they are given:
A polygon with four vertices can be cut along either of its two diagonals:
The states are ranges of vertices. The vertices form a smaller polygon: its sides are the sides of the original between those vertices, and one straight line from vertex back to vertex closes it. In the second sample, vertices 0, 1 and 2 form the triangle with the values 3, 7 and 4, closed by the diagonal from vertex 2 back to vertex 0. Let dp[l][r] be the smallest score of triangulating that smaller polygon. The whole polygon is dp[0][n - 1], and its closing line is the original side from the last vertex to the first.
A triangulation has no order, so there is no last step to look at. We look at the closing line from to instead. It lies on the boundary of the smaller polygon, so exactly one triangle has it as a side, and the third corner of that triangle is a vertex strictly between and .
The triangle scores , where stands for values[i]. On one side of it is the polygon on the vertices to , and on the other the polygon on the vertices to . Either of them may be just two neighbouring vertices, which enclose no area and score 0. The two have only vertex in common and are triangulated separately. Trying every gives the transition:
Vertex is a corner of both smaller polygons, so the two ranges are to and to , where Slimes had to and to . The base cases change with that: they are the ranges of two neighbouring vertices, with dp[l][l + 1] = 0, and the shortest range with a triangle in it has three vertices.
For the second sample, dp[0][2] is the triangle on vertices 0, 1 and 2, with score , and dp[1][3] is the triangle on vertices 1, 2 and 3, with score . The whole polygon has two candidates:
They are the two diagonals from before, and dp[0][3] is the smaller, 144.
The triangulation program
The loops are the ones from Slimes. A range now has at least three vertices, the split runs strictly between the two ends, and the cost of the triangle is added inside the loop over .
def min_score_triangulation(values):
n = len(values)
dp = [[0] * n for _ in range(n)]
for length in range(3, n + 1):
for l in range(n - length + 1):
r = l + length - 1
best = float("inf")
for k in range(l + 1, r):
triangle = values[l] * values[k] * values[r]
best = min(best, dp[l][k] + dp[k][r] + triangle)
dp[l][r] = best
return dp[0][n - 1]
print(min_score_triangulation([1, 2, 3]))
print(min_score_triangulation([3, 7, 4, 5]))
print(min_score_triangulation([1, 3, 1, 4, 1, 5]))Prints 6, 144 and 13, the answers to the three samples.
There is one candidate for each choice of three vertices . With at most 50 that is at most 19,600 candidates.
Deeper read: the cheapest order for a chain of matrix products
Many algorithms textbooks teach this transition on a different problem: choosing the order in which to multiply a chain of matrices. Multiplying an matrix by a matrix takes multiplications of numbers. A chain of several matrices can be multiplied in any bracketing, and the bracketings differ in cost. For a matrix , a matrix and a matrix :
Write the dimensions of the chain as one list, [2, 10, 3, 8], and give it to min_score_triangulation. It returns 108. A triangle with corners , and stands for multiplying a matrix by a matrix, and the two smaller polygons stand for the products that made those two matrices.
Choose the last balloon to burst
The polygon's transition also solves Burst Balloons, a problem LeetCode rates Hard, once the right states are found.
A row of balloons has a number on each, given as nums. Bursting a balloon earns its number times the numbers on the balloons to its left and right at that moment. Where a neighbour is missing, at either end of the row, use 1 in its place. The burst balloon is then removed, so the balloons on its two sides become neighbours. Return the most coins you can earn by bursting every balloon.
Constraints
-
nums[i]
Sample 1 · Input
nums = [3,1,5,8]
Output
167
Sample 2 · Input
nums = [1,5]
Output
10
In the first sample the best order bursts the 1, then the 5, then the 3, and the 8 last:
A natural first try is to let a state be a range of balloons and to choose the first balloon to burst in it, so that the balloons on its left and on its right become two separate problems. This does not work. Once the first balloon is gone, its two sides stand next to each other, and what a balloon on the left earns depends on which balloons on the right are still there.
Take the row 3, 1, 5. Its best order bursts the 1 for , then the 3 for , then the 5 for 5, which is 35 coins. The 3 earned 15 because the 5 was standing beside it. If bursting the 1 first left two separate problems, the 3 would be a row of its own on the left, and it would earn only .
The last balloon to burst does separate the row. While it is standing, no balloon on its left can become a neighbour of a balloon on its right, so the two sides are burst separately. In the first sample the 8 bursts last, so the 3, the 1 and the 5 burst while the 8 stands just to their right, with the end of the row to their left. What a side earns depends on what stands just outside its two ends, so a smaller question has to name both of them, and we make them part of the state.
Add a balloon with the number 1 at each end of the row, in place of the missing neighbours. Call the padded row , with positions 0 to . Let dp[l][r] be the most coins from bursting every balloon strictly between positions and , while the balloons at and stay standing. The answer is dp[0][m - 1].
Let be the last balloon between and to burst. At that moment every other balloon between and is gone, so its neighbours are the balloons at and , and it earns . Before that, the balloons between and burst while and are standing, and the most they can earn is dp[l][k]. The balloons between and burst while and are standing, and the most they can earn is dp[k][r]. The transition keeps the best :
As with the polygon, position is an end of both smaller ranges, and dp[l][l + 1] is 0 because no balloon lies between two neighbouring positions.
dp[0][4] is 159. No balloon lies between the 8 and the last position.The Burst Balloons program
Apart from the two added balloons and the maximum, this is the triangulation program.
def max_coins(nums):
v = [1] + nums + [1]
m = len(v)
dp = [[0] * m for _ in range(m)]
for length in range(3, m + 1):
for l in range(m - length + 1):
r = l + length - 1
for k in range(l + 1, r):
last = v[l] * v[k] * v[r]
dp[l][r] = max(dp[l][r], dp[l][k] + dp[k][r] + last)
return dp[0][m - 1]
print(max_coins([3, 1, 5, 8]))
print(max_coins([1, 5]))
print(max_coins([3, 1, 5]))Prints 167 and 10, the answers to the two samples, and 35 for the row 3, 1, 5.
The table starts at 0 and no candidate is negative, so the maximum needs no starting value of its own. With 300 balloons the padded row has 302 positions, and there is one candidate for each choice of three positions , which is 4,545,100 candidates.
Shorten a range from either end
The last problem has ranges and no splits. A range only loses a number at one of its ends.
A list holds numbers. Two players take turns, and on each turn a player removes the first or the last number of the list and adds it to their score. Both players try to make their own score as large as possible. Print the largest score the first player can get.
The first input line holds and the second the numbers .
Constraints
Sample · Input
4 4 5 1 3
Output
8
Taking the larger end each time is not the best play. In the sample, a first player who takes the 4 leaves 5, 1, 3. The second player takes the 5, and the first ends with . Taking the 3 first leaves 4, 5, 1. Whichever end the second player takes, the 5 becomes an end, and the first player finishes with .
Every turn removes an end, so the numbers still in the list are always a range of the original list. Number the positions from 0 and write for the number at position . Let dp[l][r] be the largest score that the player about to move can still collect when the numbers at positions to are left. One table serves both players, because from a given range the rest of the game is the same whichever of them is about to move. The first player moves first on the whole list, so the answer is dp[0][n - 1].
The two players share the numbers to between them, so the player to move collects the total of the range minus what the other player collects. If the mover takes , the other player moves next with the numbers to left and collects dp[l + 1][r]. If the mover takes , the other player collects dp[l][r - 1]. The mover takes the end that leaves the other player less:
The base cases are the ranges of one number. The mover takes it, so dp[l][l] is . Both candidates read a range one shorter, so the table is again filled by length. For the sample it is:
dp[0][3].The whole list has the total 13. Taking the 4 leaves the second player dp[1][3] = 6, and taking the 3 leaves them dp[0][2] = 5. So the first player takes the 3 and scores , as we found by hand.
The Removal Game program
The loops over the length and over are the ones from Slimes. There is no loop over splits, because a range has only two candidates.
def removal_game(x):
n = len(x)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + x[i]
dp = [[0] * n for _ in range(n)]
for l in range(n):
dp[l][l] = x[l]
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] = total - min(dp[l + 1][r], dp[l][r - 1])
return dp[0][n - 1]
n = int(input())
x = list(map(int, input().split()))
print(removal_game(x))On the sample the program prints 8.
Python details
For 5,000 numbers this table took about 700 MB of memory in our test, and CSES allows 512 MB. The Deeper read below keeps one diagonal of the table and needs 16 MB.
The line that fills an entry runs once for each range of two or more numbers, which is times: 12,497,500 for 5,000 numbers.
Deeper read: keep one diagonal of the table
A range of length reads only the two ranges of length inside it. The ranges of one length are one diagonal of the table, so the program can keep a single array, dp, that holds one diagonal, and reuse it for every length. Before the pass for length , dp[l] holds the value for the range of length that starts at . The pass replaces it with the value for the range of length that starts at .
def removal_game(x):
n = len(x)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + x[i]
dp = x[:]
for length in range(2, n + 1):
for l in range(n - length + 1):
r = l + length - 1
dp[l] = prefix[r + 1] - prefix[l] - min(dp[l + 1], dp[l])
return dp[0]
n = int(input())
x = list(map(int, input().split()))
print(removal_game(x))On the sample the program prints 8.
The array starts as a copy of the numbers, which are the base cases. In the line that computes the new dp[l], the old dp[l] is the range to and dp[l + 1] is the range to . The inner loop has to go through in increasing order, so that dp[l + 1] has not been replaced when that line reads it. With running downward the program prints 9 on the sample.
With CPython 3.14 on a 2025 laptop this version took 1.1 seconds for 5,000 numbers, and CSES allows 1 second. CSES also runs PyPy 3, which is the one to choose for a loop this long.
Time and space of these tables
- Slimes
time, space - About states with up to candidates each.
- Triangulation, Burst Balloons
time, space - One candidate for each three positions , about of them.
- Removal Game
time and space - One state per range with two candidates each. A length reads only the length before it, so keeping one diagonal brings the space down to .
Common mistakes
Filling the Slimes table one row at a time from the top, with first.
- Where it breaks
- For
[10, 20, 30]the program prints60, and the answer is90.dp[0][2]is computed beforedp[1][2]and reads it as 0. - The fix
- Fill the ranges in order of length, or fill the rows from the bottom up, with running from down to 0 and going up from .
Keeping the Slimes split in the triangulation program, with
dp[k + 1][r]wheredp[k][r]belongs.- Where it breaks
- For
[3, 7, 4, 5]the program returns105, and the answer is144. The candidate for adds the triangle 3, 7, 5 and then readsdp[2][3], which is 0, so the triangle 7, 4, 5 is left out. - The fix
- The third corner belongs to both smaller polygons. Read
dp[l][k]anddp[k][r].
Adding the entry of the shorter range to the number taken in Removal Game, as in
max(x[l] + dp[l + 1][r], x[r] + dp[l][r - 1]).- Where it breaks
- On the sample
4 5 1 3the program prints13, the total of the list, and the answer is8.dp[l + 1][r]is what the other player collects, and adding it gives the mover every number. - The fix
- Subtract the smaller of the two entries from the total of the range.
Check your understanding
The next problem has the states and the splits of Slimes. Read it, and then answer the question under it before opening the answer.
You get an array arr of positive integers. Consider every binary tree in which each node has either no children or two, and whose leaves, read from left to right, hold the values of arr in order. A node with children has the value of the largest leaf in its left subtree times the largest leaf in its right subtree. Return the smallest possible sum of the values of the nodes with children.
Constraints
-
arr.length -
arr[i]
Sample 1 · Input
arr = [6,2,4]
Output
32
Sample 2 · Input
arr = [4,11]
Output
44
Recall In this problem, what takes the place of the cost of the last merge, and how can the program look it up?
For [6, 2, 4] there are two trees. The root separates either the 6 from the pair 2, 4, for a sum of , or the pair 6, 2 from the 4, for .
The root of a tree over the leaves to separates them into the leaves to and the leaves to , and each side is a tree of the same kind. So the states and the splits are those of Slimes: dp[l][r] is the smallest sum for the leaves to , and dp[l][l] is 0. The root takes the place of the last merge. Its value is the largest leaf on the left times the largest leaf on the right. That depends on , so it goes inside the minimum:
Here big[l][r] is the largest value among the leaves to . It is a second table over the same ranges, filled before the main loops from big[l][l] = arr[l] and big[l][r] = max(big[l][r - 1], arr[r]), the way the prefix sums were prepared for Slimes.
Deeper read: merging k piles in one move
LeetCode has a harder version of Slimes in which one move merges exactly neighbouring piles. The problem uses the letter for that number, so in this section the split is called .
piles of stones stand in a row, and pile holds stones[i] stones. One move merges exactly consecutive piles into one pile and costs the number of stones in those piles. Return the smallest total cost of ending with one pile, or if that cannot be done.
Constraints
-
stones[i]
Sample 1 · Input
stones = [3,2,4,1], k = 2
Output
20
Sample 2 · Input
stones = [3,2,4,1], k = 3
Output
-1
Sample 3 · Input
stones = [3,5,1,2,6], k = 3
Output
25
In the third sample, merging 5, 1 and 2 costs 8 and leaves 3, 8, 6. Merging those three costs 17, and the total is 25.
A move replaces piles with one, so it lowers the number of piles by . Getting from piles down to one is possible only when is a multiple of . In the second sample is 3 and is 2, so the answer is : after one move two piles are left, and no move merges two piles when is 3.
The same count applies inside every range, so many ranges cannot be merged into one pile, and the state allows for that. Let dp[l][r] be the smallest cost of merging the piles to into as few piles as they can reach. A range of piles can get down to piles. With , for example, a range of 4 piles stops at 2.
For the transition, look at the piles the range ends with and take the leftmost one. It was made from the piles to for some , and because it is a single pile, is a multiple of . The other final piles were made from the piles to , merged as far as they go. So those piles stop at one pile fewer than the whole range can reach, and the leftmost pile makes up the difference. That gives the candidate dp[l][m] + dp[m + 1][r] for , , and so on, as long as is less than .
The exception is a range that can become one pile, which happens when is a multiple of . There the piles to stop at piles. Together with the leftmost pile they make piles, and one more move merges those into one, for the total of the range.
def merge_stones(stones, k):
n = len(stones)
if (n - 1) % (k - 1) != 0:
return -1
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + stones[i]
dp = [[0] * n for _ in range(n)]
for length in range(k, n + 1):
for l in range(n - length + 1):
r = l + length - 1
best = float("inf")
for m in range(l, r, k - 1):
best = min(best, dp[l][m] + dp[m + 1][r])
if (length - 1) % (k - 1) == 0:
best += prefix[r + 1] - prefix[l]
dp[l][r] = best
return dp[0][n - 1]
print(merge_stones([3, 2, 4, 1], 2))
print(merge_stones([3, 2, 4, 1], 3))
print(merge_stones([3, 5, 1, 2, 6], 3))Prints 20, -1 and 25, the answers to the three samples.
The loop over lengths starts at , because a shorter range allows no move and costs 0. With every is allowed and every range adds its total, which is the Slimes program.
Further reading
- USACO Guide, GoldRange DP(opens in a new tab)
Lists the signs that a problem calls for states over ranges, then solves one whose transition pairs the first letter of a range with a later equal letter. Its practice list is graded by difficulty.
- AtCoder Educational DP Contest, problem LL - Deque(opens in a new tab)
Removal Game with a different question: the first player's score minus the second player's. Slimes is problem N of the same contest.
- Jeff Erickson (PDF)Algorithms, Chapter 3: Dynamic programming(opens in a new tab)
Section 3.9 builds an optimal binary search tree with a table over ranges of keys, prepares the range totals in a second table, and compares three orders in which the table can be filled. Parts of this page adapt this chapter’s text, licensed CC BY 4.0 (creativecommons.org/licenses/by/4.0), with changed wording, examples and code.
- WikipediaMatrix chain multiplication(opens in a new tab)
The matrix problem from the Deeper read, drawn as a polygon whose triangulations are the bracketings, with the algorithm of Hu and Shing.
- OI Wiki, in Chinese区间 DP (Interval DP)(opens in a new tab)
Merging piles that stand in a circle. The row is written out twice, so that every way of cutting the circle open is a range of the doubled row.
- cp-algorithmsKnuth's Optimization(opens in a new tab)
For transitions of the Slimes form, gives the conditions under which the best split of a range lies between the best splits of the two ranges one shorter, which brings the time from down to .
