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`

312. Burst Balloons
``````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);
}
``````