7
\$\begingroup\$

https://leetcode.com/problems/burst-balloons/

Given n balloons, indexed from 0 to n-1, each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If you burst balloon i, the number of coins you will get is calculated as: $$ nums[left] * nums[i] * nums[right] $$Here, left and right are adjacent indices of i. After the burst, left and right then becomes adjacent.

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

Note:

You may imagine $$ nums[-1] = nums[n] = 1 $$They are not real therefore you can not burst them. 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Input: [3,1,5,8]
Output: 167 
Explanation: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
             coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167
using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace RecurssionQuestions
{
    /// <summary>
    /// https://leetcode.com/problems/burst-balloons/
    /// </summary>
    [TestClass]
    public class BurstBalloonsTest
    {
        [TestMethod]
        public void TestExample()
        {
            int[] nums = {3, 1, 5, 8};
            BurstBalloonsClass burst = new BurstBalloonsClass();
            Assert.AreEqual(167, burst.MaxCoins(nums));
        }
    }

    public class BurstBalloonsClass
    {

        public int MaxCoins(int[] nums)
        {
            int[] numbers = new int[nums.Length +2];  // we add 2 because of the question
            // nums[-1] = nums[n] = 1
            int n = 1;
            foreach (var x in nums)
            {
                if (x > 0) // we care only about positive values for profit
                {
                    numbers[n++] = x;
                }
            }
            numbers[0] = numbers[n++] = 1;
            int[][] memo = new int[n][];
            for (var index = 0; index < memo.Length; index++)
            {
                memo[index]= new int[n];
            }
            // we allocate NxN matrix for memoization

            return Burst(memo, numbers, 0, n - 1);
        }

        private int Burst(int[][] memo, int[] numbers, int left, int right)
        {
            if (left + 1 == right)
            {
                return 0;
            }

            if (memo[left][right] > 0)
            {
                return memo[left][right];
            }

            int ans = 0;
            // we try all the options between left and right
            // we compare the answers of all of the options and the maxmial one
            // if poped all of the ballons from left to u and from i to right we have only an option to pop
            // numbers[left] * numbers[i] * numbers[right]
            for (int i = left + 1; i < right; ++i)
            {
                ans = Math.Max(ans, numbers[left] * numbers[i] * numbers[right]
                                    + Burst(memo, numbers, left, i)
                                    + Burst(memo, numbers, i, right));
            }

            memo[left][right] = ans;
            return ans;
        }
    }
}
\$\endgroup\$
4
+50
\$\begingroup\$

Some things come to mind when I read your code.

There is a nice feature on arrays in C# called CopyTo(). It gives you the possibility to copy an array without using a loop. Like so:

int[] newNums = new int[n];
nums.CopyTo(newNums, 1); 
newNums[0] = newNums[n-1] = 1; //This line I really like. 

There is also something called a multidimensional Array which basically does the same thing as int[][]. This gives you the possibility to do this:

int[,] memo = new int[n,n];

Use them together and you can remove all your loops from int maxcoins.

Regarding your actual work method Burst I would say that you make things rather confusing. When debugging, the first thing that happens is that you cache a number series which is not allowed until 3 balloons are popped. It adds [0][1][5] to the cache. A more reasonable approach would have been [0][1][2] then [0][1][3] up to [0][1][5]. After that switch to [0][2][3] etc. When you reach [0][4][5] you start over at [1][2][3].

To do that you would have to create nested loops in your Burst method:

        for (int i = left+1; i < right; ++i)
        {
            for(int j = i+1; j<= right; ++j)
                ans = Math.Max(ans, numbers[left] * numbers[i] * numbers[j]
                                + Burst(memo, numbers, left, i)
                                + Burst(memo, numbers, i, j));
        }

However, there is an even more simple approach to this problem and that is to actually pop the balloons in the array. This can be done easiest with a list instead of an array. But both are possible. So what you would do is to create a new set of balloons after each pop. So here caching is out of the question because you never really know what range you processed before. And to be honest I guess it would most likely slow down the process and make the code harder to read. I use the same variable names as you but in reality I would name nums and numbers as balloons and newNumbers would be named remainingBalloons. I did however change the variable i to baloonToPop to make it easier to understand what it represents. I left the adding of the ones in the code because it simplifies the Burst method.

    public void MaxCoins(List<int> nums)
    {
        nums.Insert(0, 1); //Add the ones to the array
        nums.Add(1);
        int result = Burst(nums);
    }

    private int Burst(List<int> numbers)
    {
        int result = 0;
        for (int baloonToPop = 1; baloonToPop < numbers.Count-1; baloonToPop++)
        {
            List<int> newNumbers = new List<int>();
            newNumbers.AddRange(numbers);
            newNumbers.RemoveAt(baloonToPop);
            int sumFromBaloonPop = numbers[baloonToPop - 1] * numbers[baloonToPop] * numbers[baloonToPop + 1];
            result = Math.Max(result, Burst(newNumbers) + sumFromBaloonPop);
        }
        return result;
    }

To do it with an array (in case there is a library restriction) you would have to create a new Array and then copy Subranges from the initial one instead of creating a copy of the List using AddRange + RemoveAt as above:

int[] newNumbers = new int[numbers.Length-1];
Array.ConstrainedCopy(numbers, 0, newNumbers, 0, baloonToPop);
Array.ConstrainedCopy(numbers, baloonToPop + 1, newNumbers, baloonToPop, numbers.Length - (baloonToPop + 1));
\$\endgroup\$
  • 1
    \$\begingroup\$ Thorough review, have some rep from me :) \$\endgroup\$ – dfhwze Oct 11 at 19:46
  • 1
    \$\begingroup\$ @dfhwze I didn't understand why you put a bounty on my question, but thanks you and thank you guys for the reviews \$\endgroup\$ – Gilad Oct 12 at 6:47
4
\$\begingroup\$

The comment here

int[] numbers = new int[nums.Length +2];  // we add 2 because of the question

is not really useful, it requires to read the entire question to figure out why 2 is added to the number of balloons. I would suggest something like

// Allocate array for all balloons, plus the two "imaginary" balloons 
// at positions -1 and n.

which closely matches the note from the problem description:

You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.