LeetCode 312: Burst Balloons

Explanation:

This problem can be solved using dynamic programming. We can consider the balloons one by one, and for each balloon, we can calculate the maximum coins by bursting it last. We need to maintain a dynamic programming array to store the maximum coins we can get after bursting certain balloons.

1. Create a new array by inserting 1 at the beginning and end of the input array to handle edge cases.
2. Define a 2D dp array where dp[i][j] represents the maximum coins we can get by bursting balloons between indices i and j.
3. Iterate over all possible balloon ranges of different lengths, updating the dp values based on the previous calculated results.
4. The final answer will be stored in dp[1][n], where n is the length of the input array.

Time Complexity: O(n^3) Space Complexity: O(n^2)

:

class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] newNums = new int[n + 2];
        newNums[0] = newNums[n + 1] = 1;
        for (int i = 0; i < n; i++) {
            newNums[i + 1] = nums[i];
        }

        int[][] dp = new int[n + 2][n + 2];

        for (int len = 1; len <= n; len++) {
            for (int left = 1; left <= n - len + 1; left++) {
                int right = left + len - 1;
                for (int k = left; k <= right; k++) {
                    dp[left][right] = Math.max(dp[left][right], newNums[left - 1] * newNums[k] * newNums[right + 1] + dp[left][k - 1] + dp[k + 1][right]);
                }
            }
        }

        return dp[1][n];
    }
}