Interval dynamic programming

When to use it

Use it when items stand in one row, an order of joins or removals must be chosen, and a smaller task is a stretch of the row, known by its two ends.

It belongs to the optimization group: Find the best answer without trying every possibility: reuse smaller answers, or take the safe choice first.

Watch it work

Piles of sand stand in a row, and piles gives their weights. You may push two neighboring piles together into one, which costs the weight of the new pile. Return the lowest total cost of ending with one pile.

Input
piles = [4, 3, 3, 5]

Output
30

The method

1. A stretch of one pile needs no join: its cost is 0
2. Take the stretches by length, shortest first
3. Try every split into a left part and a right part
4. Keep the cheapest split and add the last join's weight
5. Return the cell for the stretch of all the piles

The run, one moment at a time

1. Step 1. Each cell is one stretch: row for its left end, column for its right end. It holds the lowest cost of making that stretch one pile, so a single pile costs 0. A ? is a cost still to come.

   piles: 4 3 3 5
   left 0: 0 ? ? ?
   left 1: · 0 ? ?
   left 2: · · 0 ?
   left 3: · · · 0
   

2. Step 2. Faded cells are never used: such a stretch would end before it starts. Stretches of two piles come first, here piles 0 to 1. A split always gives shorter stretches, whose cells are then ready.

   piles: 4 3 3 5
   left 0: 0 ? ? ?
   left 1: · 0 ? ?
   left 2: · · 0 ?
   left 3: · · · 0
   

3. Step 4. Piles 0 to 1 split in one way, into two single piles that cost 0. The join makes a pile of 4 + 3 = 7, so the cell is 7.

   piles: 4 3 3 5
   left 0: 0 7 ? ?
   left 1: · 0 ? ?
   left 2: · · 0 ?
   left 3: · · · 0
   

4. Step 4. Piles 1 to 2 are two single piles again, so the parts cost 0. The join makes a pile of 3 + 3 = 6, so the cell is 6.

   piles: 4 3 3 5
   left 0: 0 7 ? ?
   left 1: · 0 6 ?
   left 2: · · 0 ?
   left 3: · · · 0
   

5. Step 4. Piles 2 to 3 are two single piles again, so the parts cost 0. The join makes a pile of 3 + 5 = 8, so the cell is 8.

   piles: 4 3 3 5
   left 0: 0 7 ? ?
   left 1: · 0 6 ?
   left 2: · · 0 8
   left 3: · · · 0
   

6. Step 3. Piles 0 to 2 split in two places. Each split adds the cost of its left part and of its right part. After pile 0: 0 + 6 = 6. After pile 1: 7 + 0 = 7.

   piles: 4 3 3 5
   left 0: 0 7 ? ?
   left 1: · 0 6 ?
   left 2: · · 0 8
   left 3: · · · 0
   

7. Step 4. The cheapest split is after pile 0 and costs 6. The last join makes a pile of 4 + 3 + 3 = 10, so the cell is 6 + 10 = 16.

   piles: 4 3 3 5
   left 0: 0 7 16 ?
   left 1: · 0 6 ?
   left 2: · · 0 8
   left 3: · · · 0
   

8. Step 3. Piles 1 to 3 split in two places. After pile 1: 0 + 8 = 8. After pile 2: 6 + 0 = 6.

   piles: 4 3 3 5
   left 0: 0 7 16 ?
   left 1: · 0 6 ?
   left 2: · · 0 8
   left 3: · · · 0
   

9. Step 4. The cheapest split is after pile 2 and costs 6. The last join makes a pile of 3 + 3 + 5 = 11, so the cell is 6 + 11 = 17.

   piles: 4 3 3 5
   left 0: 0 7 16 ?
   left 1: · 0 6 17
   left 2: · · 0 8
   left 3: · · · 0
   

10. Step 3. Last, all four piles: they split in three places. After pile 0: 0 + 17 = 17. After pile 1: 7 + 8 = 15. After pile 2: 16 + 0 = 16.

    piles: 4 3 3 5
    left 0: 0 7 16 ?
    left 1: · 0 6 17
    left 2: · · 0 8
    left 3: · · · 0
    

11. Step 4. The cheapest split is after pile 1 and costs 15. The last join makes a pile of 4 + 3 + 3 + 5 = 15, so the cell is 15 + 15 = 30.

    piles: 4 3 3 5
    left 0: 0 7 16 30
    left 1: · 0 6 17
    left 2: · · 0 8
    left 3: · · · 0
    

12. Step 5. The cell for piles 0 to 3 holds the answer: 30. The run wrote 6 cells and tried 10 splits, and every split read cells that were ready.

    piles: 4 3 3 5
    left 0: 0 7 16 30
    left 1: · 0 6 17
    left 2: · · 0 8
    left 3: · · · 0
    

The code

The numbered comments are the steps of the method.

function solve(piles) {
  const n = piles.length;
  // 1. A stretch of one pile needs no join: its cost is 0
  const cost = [];
  for (let i = 0; i < n; i++) cost.push(new Array(n).fill(0));
  // 2. Take the stretches by length, shortest first
  for (let length = 2; length <= n; length++) {
    for (let left = 0; left + length <= n; left++) {
      const right = left + length - 1;
      // 3. Try every split into a left part and a right part
      let cheapest = Infinity;
      // k is the last pile of the left part
      for (let k = left; k < right; k++) {
        const parts = cost[left][k] + cost[k + 1][right];
        cheapest = Math.min(cheapest, parts);
      }
      // 4. Keep the cheapest split and add the last join's weight
      let weight = 0;
      for (let i = left; i <= right; i++) weight += piles[i];
      cost[left][right] = cheapest + weight;
    }
  }
  // 5. Return the cell for the stretch of all the piles
  return cost[0][n - 1];
}

def solve(piles):
    n = len(piles)
    # 1. A stretch of one pile needs no join: its cost is 0
    cost = [[0] * n for _ in range(n)]
    # 2. Take the stretches by length, shortest first
    for length in range(2, n + 1):
        for left in range(n - length + 1):
            right = left + length - 1
            # 3. Try every split into a left part and a right part
            cheapest = float("inf")
            # k is the last pile of the left part
            for k in range(left, right):
                parts = cost[left][k] + cost[k + 1][right]
                cheapest = min(cheapest, parts)
            # 4. Keep the cheapest split and add the last join's weight
            weight = 0
            for i in range(left, right + 1):
                weight += piles[i]
            cost[left][right] = cheapest + weight
    # 5. Return the cell for the stretch of all the piles
    return cost[0][n - 1]

How to spot it

Given: Only neighbors in the row can be joined or combined

Whatever is joined last is made from a left part and a right part, and each part is a shorter stretch of the same row.

Given: Each operation changes which items are next to each other

Then the first operation is hard to reason about. Ask which operation of a stretch comes last: its two sides never meet, so they are solved apart.

Asked: The best total over every order of doing the operations

The orders are far too many to try one by one. Many orders share the same stretches, so each stretch is solved once and reused.

Limits: The row has at most a few hundred items

Every stretch with every split is about 4.5 million steps for 300 items. A limit this small leaves room for such a table.

Looks like it, but is not

• The table has two indices, and they are positions in two different inputs, such as two words. Use Two-dimensional dynamic programming. There a cell is a beginning of each input, filled row by row. Here both indices are ends of one stretch, and the table is filled by length.
• A row must be cut into pieces, and what a piece is worth depends only on the piece itself. Use One-dimensional dynamic programming. The best answer for each beginning of the row is enough, so one index does it. The pieces are never joined again.
• Any two piles may be joined, not only neighbors, and a join costs the size of the new pile. Use Heap as a priority queue. Without the row, joining the two smallest piles is always safe, so no table is needed. A heap hands out the two smallest each time.

Cost and mistakes

There are about n × n / 2 stretches and each tries up to n splits, so time is about n × n × n steps, written O(n^3). Extra space is the table of n × n cells, written O(n^2).

Watch out

• Do not fill the table row by row from the top. The cell of a long stretch reads cells in lower rows, so go by length: then every shorter stretch is ready.
• Joining the cheapest neighbors first is not safe. In the example that order costs 31, and the table finds 30. An early join changes what later joins cost, so every split must be compared.

In the 150

One problem of the 150 uses it. Naming them gives their method away, so the list is folded.