The best reward inside (l,k), the best reward inside (k,r), and a[l]×a[k]×a[r] for the final pop. The two outer boundaries stay alive while both smaller intervals are solved.

best[l][r] excludes the boundary balloons. Every complete popping order has some last k, so trying all such k covers every solution. Before k is popped, it separates the two sides, making their rewards independent under the fixed-boundary contract. Empty intervals between adjacent boundaries return zero. Fill increasing boundary distance so both shorter intervals are ready. This last-action choice is the key reasoning step, not merely recognizing a two-index table.

What the function promises: nums contains nonnegative balloon values. Return the largest reward from bursting all balloons, with virtual value-one boundaries. Empty input returns zero; input is not modified.

def burst_reward(nums):
    values = [1] + list(nums) + [1]
    n = len(values)
    best = [[0] * n for _ in range(n)]
    for gap in range(2, n):
        for left in range(n - gap):
            right = left + gap
            best[left][right] = max(
                best[left][last] + best[last][right]
                + values[left] * values[last] * values[right]
                for last in range(left + 1, right))
    return best[0][n - 1]

assert burst_reward([2, 3]) == 9
assert burst_reward([3, 1, 5, 8]) == 167
assert burst_reward([0, 0]) == 0
assert burst_reward([]) == 0

Work and storage: O(n³) time and O(n²) space for n balloons: quadratic intervals, linear last-pop choices per interval. Bottom-up evaluation avoids deep recursion.

When to recognize it: Choose which balloon goes last inside fixed boundaries. Its final neighbors become known.

Check before applying it: Choosing the first balloon joins its two sides, so they are not independent fixed-boundary subproblems.

The first pop removes their separator, letting remaining balloons from opposite sides become neighbors. The fixed-boundary subproblem contract is no longer valid. Independence is earned by choosing the last pop, not assumed from the picture.