Welcome to Subscribe On Youtube

312. Burst Balloons

Description

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 <= 300
  • 0 <= nums[i] <= 100

Solutions

  • class Solution {
        public int maxCoins(int[] nums) {
            int[] vals = new int[nums.length + 2];
            vals[0] = 1;
            vals[vals.length - 1] = 1;
            System.arraycopy(nums, 0, vals, 1, nums.length);
            int n = vals.length;
            int[][] dp = new int[n][n];
            for (int l = 2; l < n; ++l) {
                for (int i = 0; i + l < n; ++i) {
                    int j = i + l;
                    for (int k = i + 1; k < j; ++k) {
                        dp[i][j]
                            = Math.max(dp[i][j], dp[i][k] + dp[k][j] + vals[i] * vals[k] * vals[j]);
                    }
                }
            }
            return dp[0][n - 1];
        }
    }
    
  • class Solution {
    public:
        int maxCoins(vector<int>& nums) {
            nums.insert(nums.begin(), 1);
            nums.push_back(1);
            int n = nums.size();
            vector<vector<int>> dp(n, vector<int>(n));
            for (int l = 2; l < n; ++l) {
                for (int i = 0; i + l < n; ++i) {
                    int j = i + l;
                    for (int k = i + 1; k < j; ++k) {
                        dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]);
                    }
                }
            }
            return dp[0][n - 1];
        }
    };
    
  • class Solution:
        def maxCoins(self, nums: List[int]) -> int:
            nums = [1] + nums + [1]
            n = len(nums)
            dp = [[0] * n for _ in range(n)]
            for l in range(2, n):
                for i in range(n - l):
                    j = i + l
                    for k in range(i + 1, j):
                        dp[i][j] = max(
                            dp[i][j], dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]
                        )
            return dp[0][-1]
    
    
  • func maxCoins(nums []int) int {
    	vals := make([]int, len(nums)+2)
    	for i := 0; i < len(nums); i++ {
    		vals[i+1] = nums[i]
    	}
    	n := len(vals)
    	vals[0], vals[n-1] = 1, 1
    	dp := make([][]int, n)
    	for i := 0; i < n; i++ {
    		dp[i] = make([]int, n)
    	}
    	for l := 2; l < n; l++ {
    		for i := 0; i+l < n; i++ {
    			j := i + l
    			for k := i + 1; k < j; k++ {
    				dp[i][j] = max(dp[i][j], dp[i][k]+dp[k][j]+vals[i]*vals[k]*vals[j])
    			}
    		}
    	}
    	return dp[0][n-1]
    }
    
  • function maxCoins(nums: number[]): number {
        let n = nums.length;
        let dp = Array.from({ length: n + 1 }, v => new Array(n + 2).fill(0));
        nums.unshift(1);
        nums.push(1);
        for (let i = n - 1; i >= 0; --i) {
            for (let j = i + 2; j < n + 2; ++j) {
                for (let k = i + 1; k < j; ++k) {
                    dp[i][j] = Math.max(nums[i] * nums[k] * nums[j] + dp[i][k] + dp[k][j], dp[i][j]);
                }
            }
        }
        return dp[0][n + 1];
    }
    
    
  • impl Solution {
        pub fn max_coins(nums: Vec<i32>) -> i32 {
            let n = nums.len();
            let mut arr = vec![1; n + 2];
            for i in 0..n {
                arr[i + 1] = nums[i];
            }
    
            let mut f = vec![vec![0; n + 2]; n + 2];
            for i in (0..n).rev() {
                for j in i + 2..n + 2 {
                    for k in i + 1..j {
                        f[i][j] = f[i][j].max(f[i][k] + f[k][j] + arr[i] * arr[k] * arr[j]);
                    }
                }
            }
            f[0][n + 1]
        }
    }
    
    

All Problems

All Solutions