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.length1 <= n <= 5000 <= nums[i] <= 100struct 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);
}