312. Burst Balloons Hard

1/**
2 * [312] Burst Balloons
3 *
4 * 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.
5 * If you burst the i^th 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.
6 * Return the maximum coins you can collect by bursting the balloons wisely.
7 *  
8 * Example 1:
9 * 
10 * Input: nums = [3,1,5,8]
11 * Output: 167
12 * Explanation:
13 * nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
14 * coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167
15 * Example 2:
16 * 
17 * Input: nums = [1,5]
18 * Output: 10
19 * 
20 *  
21 * Constraints:
22 * 
23 * 	n == nums.length
24 * 	1 <= n <= 300
25 * 	0 <= nums[i] <= 100
26 * 
27 */
28pub struct Solution {}
29
30// problem: https://leetcode.com/problems/burst-balloons/
31// discuss: https://leetcode.com/problems/burst-balloons/discuss/?currentPage=1&orderBy=most_votes&query=
32
33// submission codes start here
34
35impl Solution {
36    pub fn max_coins(nums: Vec<i32>) -> i32 {
37        0
38    }
39}
40
41// submission codes end
42
43#[cfg(test)]
44mod tests {
45    use super::*;
46
47    #[test]
48    fn test_312() {
49    }
50}
51