Table of Contents

# Burst Balloons – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

You are given `n`

balloons, indexed from `0`

to `n - 1`

. 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 `i`

balloon, you will get ^{th}`nums[i - 1] * nums[i] * nums[i + 1]`

coins. If `i - 1`

or `i + 1`

goes out of bounds of the array, then treat it as if there is a balloon with a `1`

painted on it.

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

**Example 1:**

Input:nums = [3,1,5,8]Output:167Explanation: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

**Example 2:**

Input:nums = [1,5]Output:10

**Constraints:**

`n == nums.length`

`1 <= n <= 300`

`0 <= nums[i] <= 100`

# C++ Burst Balloons LeetCode Solution

```
``````
class Solution {
public:
int n;
int t[501][501]; // For memoization
int solve(vector<int> &nums, int i, int j){
// BASE CASES
if(i > j)
return 0;
if(i == j){ // Only one element exists
int temp = nums[i];
if(i - 1 >= 0)
temp *= nums[i - 1];
if(i + 1 < n)
temp *= nums[i + 1];
return temp;
}
if(t[i][j] != -1) // Check if the solution is already stored for this subproblem
return t[i][j];
int ans = 0;
// For all elements in the range i to j, we choose all of them one by one
// to make them the last balloon to be burst.
for(int k = i; k <= j; k++){
// Burst the kth balloon after bursting (i, k - 1) and (k + 1, j) balloons
int temp = nums[k];
if(j + 1 < n) // As balloon j + 1 will become adjacent to k after bursting k + 1 to j balloons
temp *= nums[j + 1];
if(i - 1 >= 0) // As balloon i- 1 will become adjacent to k after bursting i to k -1 balloons
temp *= nums[i - 1];
// Recursively solve the left and right subproblems and add their contribution
temp += (solve(nums, i, k - 1) + solve(nums, k + 1, j));
// If this choice of k yields a better answer
ans = max(ans, temp);
}
return t[i][j] = ans;
}
int maxCoins(vector<int>& nums) {
memset(t, -1, sizeof(t));
// Insert two dummy balloons of value 1 to handle the balloons on the corner.
vector<int> arr = {1};
for(int x: nums)
arr.push_back(x);
arr.push_back(1);
n = arr.size();
//Start from i = 1 and j = arr.size() - 2 since first and last balloons are dummy.
return solve(arr, 1, arr.size() - 2);
}
};
```

# Java Burst Balloons LeetCode Solution

```
``````
public int maxCoins(int[] nums) {
int[][] dp = new int[nums.length][nums.length];
return maxCoins(nums, 0, nums.length - 1, dp);
}
public int maxCoins(int[] nums, int start, int end, int[][] dp) {
if (start > end) {
return 0;
}
if (dp[start][end] != 0) {
return dp[start][end];
}
int max = nums[start];
for (int i = start; i <= end; i++) {
int val = maxCoins(nums, start, i - 1, dp) +
get(nums, i) * get(nums, start - 1) * get(nums, end + 1) +
maxCoins(nums, i + 1, end, dp);
max = Math.max(max, val);
}
dp[start][end] = max;
return max;
}
public int get(int[] nums, int i) {
if (i == -1 || i == nums.length) {
return 1;
}
return nums[i];
}
```

# Python 3 Burst Balloons LeetCode Solution

```
``````
class Solution:
def maxCoins(self, A):
A, n = [1] + A + [1], len(A) + 2
dp = [[0] * n for _ in range(n)]
for i in range(n - 2, -1, -1):
for j in range(i + 2, n):
dp[i][j] = max(A[i]*A[k]*A[j] + dp[i][k] + dp[k][j] for k in range(i + 1, j))
return dp[0][n-1]
```

Array-1180

String-562

Hash Table-412

Dynamic Programming-390

Math-368

Sorting-264

Greedy-257

Depth-First Search-256

Database-215

Breadth-First Search-200

Tree-195

Binary Search-191

Matrix-176

Binary Tree-160

Two Pointers-151

Bit Manipulation-140

Stack-133

Heap (Priority Queue)-117

Design-116

Graph-108

Simulation-103

Prefix Sum-96

Backtracking-92

Counting-86

Sliding Window-73

Linked List-69

Union Find-66

Ordered Set-48

Monotonic Stack-47

Recursion-43

Trie-41

Binary Search Tree-40

Divide and Conquer-40

Enumeration-39

Bitmask-37

Queue-33

Memoization-32

Topological Sort-31

Geometry-30

Segment Tree-27

Game Theory-24

Hash Function-24

Binary Indexed Tree-21

Interactive-18

Data Stream-17

String Matching-17

Rolling Hash-17

Shortest Path-16

Number Theory-16

Combinatorics-15

Randomized-12

Monotonic Queue-9

Iterator-9

Merge Sort-9

Concurrency-9

Doubly-Linked List-8

Brainteaser-8

Probability and Statistics-7

Quickselect-7

Bucket Sort-6

Suffix Array-6

Minimum Spanning Tree-5

Counting Sort-5

Shell-4

Line Sweep-4

Reservoir Sampling-4

Eulerian Circuit-3

Radix Sort-3

Strongly Connected Componen-t2

Rejection Sampling-2

Biconnected Component-1

## Leave a comment below