Burst Balloons

Problem: You are given n balloons. 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. After the burst, the i - 1 and i + 1 then becomes adjacent.

Return the maximum coins you can collect by bursting the balloons wisely.

Example:

Input: nums = [6, 11]
Output: 77
Explanation:
First burst nums[0] then coins earned = 1 * 6 * 11 = 66
then burst nums[1] then coin earned =  1*11*1 = 11 so total coins earned are 66 + 11 = 77

Approach: We are going to use DP here. We are going to use 2D table say Table where Table[i][j] will tell the maximum coins earned for sub array nums[i...j]. Obviously Table[0][n - 1] will be our answer.

Now let's see how to fill this table:

1. FOR len = 1 to Length // for every possible length or every subarray
• For left = 0  to Length - len // left index of subarray
• right = i +  len - 1 // Right index of sub array so target sub array is (left...right)
• For last = left to right // Max coin earned by considering each element of sub array as last balloon to burst
• leftValue = nums[left - 1] // all the balloons are burst so we need to take the left of the subarray
• rightValue = nums[right + 1] // all the balloons are burst so we need to take the right of the subarray
• numOfCoinsEarnedBeforeLastBalloonBurst = Table[left][last - 1] // coins earned from left subarray of last balloon which will be (left...last-1)
• numOfCoinsEarnedAfterLastBalloonBurst = Table[last + 1][right] // coins earned from right subarray of last balloon which will be (last + 1...right)
• currentValue = leftValue * nums[last] * rightValue + numOfCoinsEarnedBeforeLastBalloonBurst + numOfCoinsEarnedAfterLastBalloonBurst 
• Table[left][right] = MAX(currentValue, Table[left][right]).

As usual we need to take care of corner cases in above steps which you can see in the implementation. That's all!

Implementation in C#:

        public int MaxCoinsByBurstingBalloons(int[] nums)

        {

            if (nums?.Length == 0)

            {

                return 0;

            }

            int[,] table = new int[nums.Length, nums.Length];

            for (int length = 1; length <= nums.Length; ++length)

            {

                for (int i = 0; i <= nums.Length - length; ++i)

                {

                    int j = i + length - 1;

                    for (int k = i; k <= j; ++k)

                    {

                        int left = i == 0 ? 1 : nums[i - 1];

                        int right = j == nums.Length - 1 ? 1 : nums[j + 1];

                        int beforeCoins = k == i ? 0 : table[i, k - 1];

                        int afterCoins = k == j ? 0 : table[k + 1, j];

                        table[i, j] = Math.Max(table[i, j], left * nums[k] * right + beforeCoins + afterCoins);

                    }

                }

            }

            return table[0, nums.Length - 1];

        }

Complexity: O(n^3)