https://leetcode.com/problems/burst-balloons/
Given
n
balloons, indexed from0
ton-1
, each balloon is painted with a number on it represented by arraynums
. You are asked to burst all the balloons. If you burst ballooni
, the number of coins you will get is calculated as: $$ nums[left] * nums[i] * nums[right] $$Here,left
andright
are adjacent indices ofi
. After the burst,left
andright
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]
≤ 100Example: 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;
}
}
}