Burst balloons

Array Dynamic Programming

63.0% acceptance

Jan 12, 2026

9729

286

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons. If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it. Return the maximum coins you can collect by bursting the balloons wisely.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn max_coins(nums: Vec<i32>) -> i32 {
    let mut balloons = vec![1];
    for &num in &nums {
      if num > 0 {
        balloons.push(num);
      }
    }
    balloons.push(1);
    
    let n = balloons.len();
    let mut dp = vec![vec![0; n]; n];
    
    for len in 2..n {
      for left in 0..n-len {
        let right = left + len;
        for i in left+1..right {
          dp[left][right] = dp[left][right].max(
            dp[left][i] + balloons[left] * balloons[i] * balloons[right] + dp[i][right]
          );
        }
      }
    }
    
    dp[0][n-1]
  }
}