Burst Balloons


Problem

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

If you burst the ithi^{th} balloon, you will get numsi1×numsi×numsi+1nums_{i - 1} \times nums_i \times nums_{i + 1} coins. If i1i - 1 or i+1i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 11 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

  • 1n3001 \leq n \leq 300
  • 0numsi1000 \leq nums_i \leq 100

Submit your solution at here

Solution

Approach

  • Let f(i,j)f(i,j) be the maximum score if we only play within the range [i,j][i,j]
  • Let g(i,j,x)g(i,j,x) be the maximum score if we only play within the range [i,j][i,j] and we pop balloon xx last
  • We will calculate ff and gg recursively :
    • g(i,j,x)=(numx×numsi1×numsj+1)+f(i,x1)+f(x+1,j)g(i,j,x) = (num_x \times nums_{i-1} \times nums_{j+1}) + f(i,x-1) + f(x+1,j)
    • f(i,j)=max(g(i,j,x))f(i,j) = max(g(i,j,x))
  • The answer is f(0,n1)f(0,n-1)

Complexity

  • Time complexity: O(n3)O(n^3)
  • Space complexity: O(n2)O(n^2)

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];
    }
}