leetcode-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 get:
# nums[i - 1] * nums[i] * nums[i + 1] coins.
# If i - 1 or i + 1 goes out of bounds, treat it as if there is a balloon with 1.
# Return the maximum coins you can collect by bursting the balloons wisely.
#
# Example 1:
# Input: nums = [3,1,5,8]
# Output: 167
# Explanation:
# burst 1, get 3*1*5 = 15
# burst 5, get 3*5*8 = 120
# burst 3, get 1*3*8 = 24
# burst 8, get 1*8*1 = 8
# Total: 15 + 120 + 24 + 8 = 167
#
# Example 2:
# Input: nums = [1,5]
# Output: 10
#
# Constraints:
# n == nums.length
# 1 <= n <= 300
# 0 <= nums[i] <= 100

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        # Add boundary balloons with value 1
        nums = [1] + nums + [1]
        n = len(nums)

        # dp[left][right] = max coins from bursting balloons (left+1, right-1)
        # Excluding left and right themselves
        dp = [[0] * n for _ in range(n)]

        # Iterate over all possible lengths
        for length in range(2, n):
            for left in range(n - length):
                right = left + length

                # Try bursting each balloon k in range (left, right) as LAST
                for k in range(left + 1, right):
                    # If k is burst last in (left, right):
                    # - Left subrange (left, k) already burst
                    # - Right subrange (k, right) already burst
                    # - Coins from bursting k: nums[left] * nums[k] * nums[right]
                    coins = nums[left] * nums[k] * nums[right]
                    coins += dp[left][k] + dp[k][right]
                    dp[left][right] = max(dp[left][right], coins)

        return dp[0][n-1]

    # Approach 2: Memoization (Top-down)
    def maxCoins2(self, nums: List[int]) -> int:
        nums = [1] + nums + [1]
        memo = {}

        def dp(left, right):
            if left + 1 == right:
                return 0

            if (left, right) in memo:
                return memo[(left, right)]

            max_coins = 0
            for k in range(left + 1, right):
                coins = nums[left] * nums[k] * nums[right]
                coins += dp(left, k) + dp(k, right)
                max_coins = max(max_coins, coins)

            memo[(left, right)] = max_coins
            return max_coins

        return dp(0, len(nums) - 1)

# Time Complexity: O(n^3) - three nested loops
# Space Complexity: O(n^2) - DP table
#
# Key Insight: Reverse Thinking
# Don't think: "Which balloon to burst first?"
# Think: "Which balloon to burst LAST in this range?"
#
# Why this works:
# - If we burst balloon k last in range [left, right]
# - All balloons between left and k are already burst
# - All balloons between k and right are already burst
# - So bursting k gives: nums[left] * nums[k] * nums[right]
# - Plus the coins from the two subproblems
#
# Visualization for [3,1,5,8]:
# Add boundaries: [1,3,1,5,8,1]
# Try each balloon as last to burst in each subrange
#
# DP Recurrence:
# dp[left][right] = max(
#   dp[left][k] + nums[left]*nums[k]*nums[right] + dp[k][right]
#   for k in range(left+1, right)
# )
#
# AirBnB: Tests advanced DP and interval optimization