Hiring process8 levels
  1. 1 IQ Test
  2. 2 Additional Online Test (If Required)
  3. 3 Office Interview with Hiring Manager
  4. 4 Unpaid Test Task (Motivation Check)
  5. 5 Paid Test Task and Follow-Up Interview
  6. 6 Iterative Paid Test Tasks
  7. 7 Office Verification
  8. 8 Final Interview with the Founder

Problems > Bursting Balloons > Editorial

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 ai·ak·aj with the two independent sub-intervals. Pad with 1s.

Complexity: O(N3)

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