# Burst Balloons

## Problem

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 $i^{th}$ balloon, you will get $nums_{i - 1} \times nums_i \times 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

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

• $1 \leq n \leq 300$
• $0 \leq nums_i \leq 100$

## Solution

### Approach

• Let $f(i,j)$ be the maximum score if we only play within the range $[i,j]$
• Let $g(i,j,x)$ be the maximum score if we only play within the range $[i,j]$ and we pop balloon $x$ last
• We will calculate $f$ and $g$ recursively :
• $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))$
• The answer is $f(0,n-1)$

### Complexity

• Time complexity: $O(n^3)$
• Space complexity: $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];
}
}
Made with love using Svelte, Three.js