Burst Balloons [Top - Down]

XXX. Burst Balloons

Dynamic Programming

Recursion

Problem Statement:

You are given an array of positive integers nums representing balloons, where each integer represents the coins you get for bursting that balloon. After a balloon is burst, it disappears, and adjacent balloons become neighbors.

Your task is to determine the maximum coins you can collect by bursting the balloons wisely.

Algorithm:

The problem is solved using a recursive dynamic programming approach:

1. Add virtual balloons with value 1 at the start and end of the array to simplify calculations.
2. Use a memoization table memo to store the maximum coins that can be collected for subarrays defined by left and right boundaries.
3. For each subarray, try bursting every balloon in the range and recursively calculate the maximum coins for the left and right partitions.
4. Update the memoization table with the maximum coins collected for the current subarray.

Complexity:

Time Complexity: O(n³), where n is the length of the balloons array (including virtual balloons). Each subarray computation involves iterating through all elements and solving smaller subproblems.
Space Complexity: O(n²), for the memoization table.

Java Implementation:

class Solution {
    public int maxCoins(int[] nums) {
        // Add virtual balloons at the boundaries
        int[] balloons = new int[nums.length + 2];
        balloons[0] = balloons[balloons.length - 1] = 1;
        for (int i = 1; i < balloons.length - 1; i++) {
            balloons[i] = nums[i - 1];
        }

        // Memoization table
        int[][] memo = new int[balloons.length][balloons.length];

        // Compute the maximum coins
        return burst(balloons, 0, balloons.length - 1, memo);
    }

    private int burst(int[] balloons, int left, int right, int[][] memo) {
        if (left + 1 == right) return 0; // No balloons to burst

        if (memo[left][right] > 0) return memo[left][right]; // Return cached result

        int max = 0;
        // Try bursting each balloon in the range [left + 1, right - 1]
        for (int i = left + 1; i < right; i++) {
            int curr = burst(balloons, left, i, memo) + burst(balloons, i, right, memo);
            curr += balloons[left] * balloons[i] * balloons[right]; // Coins from bursting
            max = Math.max(max, curr);
        }

        memo[left][right] = max; // Store result in memoization table
        return max;
    }
}

Explanation:

The algorithm uses a recursive approach to calculate the maximum coins collected for subarrays of balloons. Memoization ensures that overlapping subproblems are solved only once, reducing redundant computations.

• Virtual Balloons: Adding 1 at the boundaries simplifies calculations for edge cases.
• Recursive Calculation: For each subarray, the algorithm tries bursting every possible balloon and calculates the maximum coins for the resulting partitions.
• Memoization: Stores results of subproblems to avoid recalculating them.