#312

Burst Balloons

hard· 2-D DPruns: 0

You are given n balloons indexed from 0 to n - 1. Each balloon is painted with a number on it represented by the array nums. You are asked to burst all the balloons. If you burst the ith balloon, you get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 is out of bounds, 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.

wpm 0acc 100%time 0:000 / 595

class Solution:
    def maxCoins(self, nums: list[int]) -> int:
        nums = [1] + nums + [1]
        n = len(nums)
        dp = [[0] * n for _ in range(n)]
        for length in range(2, n):
            for left in range(n - length):
                right = left + length
                for k in range(left + 1, right):
                    dp[left][right] = max(
                        dp[left][right],
                        nums[left] * nums[k] * nums[right]
                        + dp[left][k]
                        + dp[k][right],
                    )
        return dp[0][n - 1]

click the box to focus · tab inserts 4 spaces · backspace to correct · esc to pause

desktop only

codedrill is a typing game and needs a real keyboard. open this on a laptop or desktop to practice.

you can still browse problems and sections from your phone.