Burst Balloons

Problem

You are given balloons, indexed from to . Each balloon is painted with a number on it represented by an array . You are asked to burst all the balloons.

If you burst the balloon, you will get coins. If or goes out of bounds of the array, then treat it as if there is a balloon with a painted on it.

Return the maximum coins you can collect by bursting the balloons wisely.

Example

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

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

Constraints

Submit your solution at here

Solution

Approach

  • Let be the maximum score if we only play within the range
  • Let be the maximum score if we only play within the range and we pop balloon last
  • We will calculate and recursively :
  • The answer is

Complexity

  • Time complexity:
  • Space complexity:

Code

use std::cmp::max;
impl Solution {
    pub fn max_coins(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut f = vec![vec![0;n];n];
        // f(i,j) = if we only play in the range [i,j], what is the maximum score?
        for len in 0..n {
            for i in 0..n-len {
                let j = i+len;
                for x in i..=j {
                    // in the range [i,j], if we burst balloon x last, what is the maximum score?
                    let mut score = nums[x];
                    if i > 0 {
                        score *= nums[i-1];
                    }
                    if j < n-1 {
                        score *= nums[j+1];
                    }
                    if x > i {
                        score += f[i][x-1];
                    }
                    if x < j {
                        score += f[x+1][j];
                    }
                    f[i][j] = max(f[i][j], score);
                }
            }
        }
        return f[0][n-1];
    }
}