# Burst Balloons

This page explains Java solution to problem `Burst Balloons` using `Dynamic Programming` algorithm.

## Problem Statement

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 the you burst balloon `i` you will get `nums[left] * nums[i] * nums[right]`> coins. Here `left` and `right` are adjacent indices of `i`. After the burst, the `left` and `right` then becomes adjacent.

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

Example 1:

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

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

class BurstBalloons {
public int maxCoins(int[] nums) {
if(nums == null || nums.length == 0) return 0;

int n = nums.length;
int[][] dp = new int[n][n];

for(int l = 0; l < n; l++) {
for(int from = 0; from + l < n; from++) {
int to = from + l;

int leftValue = from - 1 >= 0 ? nums[from - 1] : 1;
int rightValue = to + 1 < nums.length ? nums[to + 1] : 1;

if(l == 0) {
dp[from][to] = nums[from] * rightValue * leftValue;
}
else {
for(int burstLast = from; burstLast <= to; burstLast++) {
int before = burstLast - 1 >= 0 ? dp[from][burstLast - 1] : 0;
int after  = burstLast + 1 < n ? dp[burstLast + 1][to] : 0;
dp[from][to] = Math.max(dp[from][to], before + after + nums[burstLast] * rightValue * leftValue);
}
}
}
}
return dp[0][n - 1];
}
}
``````

## Time Complexity

O(N3) Where
N is total number of elements in an input array.

O(N2)