This page explains Java solution to problem `Burst Balloons`

using `Dynamic Programming`

algorithm.

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.

Input: [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

```
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];
}
}
```

O(N

^{3}) Where

N is total number of elements in an input array.

O(N

^{2})