Bursting Balloons — Solution & Editorial

Back to the Problem

Interval DP on the LAST balloon to burst in a range: dp[i][j] considering k as last-burst in (i, j) contributes a_i·a_k·a_j with the two independent sub-intervals. Pad with 1s.

Complexity: O(N³)

Watch out: Think of the LAST balloon burst in an interval, not the first — the neighbours are then fixed.