Tables over ranges

The state is a range, and the trick is choosing which element to think about last.

Key idea

Pad the ends so the neighbors always exist

The elements just outside the range may not exist at the array's edges. Adding a sentinel value at each end, chosen so it does not affect the arithmetic, removes every boundary case.

For a product, the identity is one. This is the same sentinel idea as U4's zero-height bar and U5's infinities: invent a value that makes the edge behave like the middle.

With the padding in place, every choice of which element goes last splits the range into two independent halves. Here are the choices for the whole range, with the two halves each one leaves behind.

1values = [3, 1, 5, 8]2padded = [1] + values + [1]3left, right = 0, len(padded) - 1       # the whole range, boundaries included4 5for last in range(left + 1, right):6    gained = padded[left] * padded[last] * padded[right]7    print(f"last removed is {padded[last]}: gains {gained},"8          f" leaves ranges ({left}, {last}) and ({last}, {right})")

Both sentinels are 1, so the outermost gains are just the element itself. Inner ranges see real neighbors.

Quick check· 5 min

Why think about the last one?

In an interval table over removals, why is it easier to reason about which element is removed last rather than first?

Because when it is removed last, its neighbors are the fixed elements just outside the range, so the two sides are independent subrangesBecause removing the last element is always cheaper than removing the firstBecause it makes the table symmetric, halving the workThere is no difference; both framings give the same recurrence

Problem· 40 min

Burst Balloons

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1values = [3, 1, 5, 8]2padded = [1] + values + [1]3left, right = 0, len(padded) - 1 # the whole range, boundaries included4 5for last in range(left + 1, right):6 gained = padded[left] * padded[last] * padded[right]7 print(f"last removed is {padded[last]}: gains {gained},"8 f" leaves ranges ({left}, {last}) and ({last}, {right})")