RUST GYM v0.2.11

312. Burst Balloons

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.

 

Example 1:

Input: nums = [3,1,5,8]
Output: 167
Explanation:
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167

Example 2:

Input: nums = [1,5]
Output: 10

 

Constraints:

  • n == nums.length
  • 1 <= n <= 500
  • 0 <= nums[i] <= 100

Rust Solution

struct Solution;

impl Solution {
    fn max_coins(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut new_nums = vec![1; n + 2];
        new_nums[1..n + 1].clone_from_slice(&nums);
        let n = new_nums.len();
        let mut memo: Vec<Vec<i32>> = vec![vec![0; n]; n];
        Self::dp(0, n - 1, &mut memo, &new_nums)
    }

    fn dp(l: usize, r: usize, memo: &mut Vec<Vec<i32>>, nums: &[i32]) -> i32 {
        if l + 1 == r {
            return 0;
        }
        if memo[l][r] != 0 {
            return memo[l][r];
        }
        let mut res = 0;
        for i in l + 1..r {
            let sum = nums[l] * nums[i] * nums[r]
                + Self::dp(l, i, memo, nums)
                + Self::dp(i, r, memo, nums);
            res = res.max(sum);
        }
        memo[l][r] = res;
        res
    }
}

#[test]
fn test() {
    let nums = vec![3, 1, 5, 8];
    let res = 167;
    assert_eq!(Solution::max_coins(nums), res);
}

Having problems with this solution? Click here to submit an issue on github.