🎓 A1Learner
🔍

DSA The Interval DP Pattern

Interval dynamic programming stores one answer for every contiguous range of a list. Short ranges are solved first so longer ranges can reuse their answers.

Length one is free

A single panel needs no join at all. Its joining cost is zero by definition.

def join_cost(i, j):
    if i == j:
        return 0
    return None

print(join_cost(2, 2))

One split, one candidate

Splitting a range at k joins the two solved parts. The join itself charges the full range length.

left = 0
right = 0
range_length = 5
candidate = left + right + range_length
print(candidate)

Lengths rise in order

The fill order visits length one, then two, then three. Every split part is shorter than the whole range.

n = 4
order = []
for length in range(1, n + 1):
    order.append(length)
print(order)

Example

def join_table(values):
    n = len(values)
    table = [[0] * n for _ in range(n)]
    splits_tried = 0
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            best = None
            for k in range(i, j):
                splits_tried += 1
                cand = table[i][k] + table[k + 1][j] + (j - i + 1)
                if best is None or cand < best:
                    best = cand
            table[i][j] = best
    return table, splits_tried


panels = [4, 2, 5, 1, 3]
table, tried = join_table(panels)
print("panels:", panels)
for length in range(1, len(panels) + 1):
    row = []
    for i in range(len(panels) - length + 1):
        j = i + length - 1
        row.append(table[i][j])
    print("length", length, "costs:", row)
print("cheapest full join:", table[0][len(panels) - 1])
print("splits tried:", tried)

Key points

  • The state is a pair of ends naming one contiguous range
  • Ranges are filled in order of growing length
  • The split point is the choice tried at every inner position
  • Each split combines two shorter ranges that are already solved
  • A range of length one is the base case and needs no split

In this example, five panels are joined into one piece at minimum total charge. Joining a range charges its length on top of the two part costs. The table fills length by length, so every needed part is ready. The cheapest full join costs 12, and the search tried 20 splits.

Note

The number of ranges grows with the square of the list length

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

Why does the fill order go from short ranges to long ranges?