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.

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

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(N³) Where
N is total number of elements in an input array.

Space Complexity

O(N²)