ronith
10/9/2018 - 8:42 AM

Burst Balloon to maximize coins

We have been given N balloons, each with a number of coins associated with it. On bursting a balloon i, the number of coins gained is equal to A[i-1]A[i]A[i+1]. Also, balloons i-1 and i+1 now become adjacent. Find the maximum possible profit earned after bursting all the balloons. Assume an extra 1 at each boundary.

Examples:

Input : 5, 10 Output : 60 Explanation - First Burst 5, Coins = 1510 Then burst 10, Coins+= 1101 Total = 60

Input : 1, 2, 3, 4, 5 Output : 110 A recursive solution is discussed here. We can solve this problem using dynamic programming. First, consider a sub-array from indices Left to Right(inclusive). If we assume the balloon at index Last to be the last balloon to be burst in this sub-array, we would say the coined gained to be-A[left-1]A[last]A[right+1]. Also, the total Coin Gained would be this value, plus dp[left][last – 1] + dp[last + 1][right], where dp[i][j] means maximum coin gained for sub-array with indices i, j. Therefore, for each value of Left and Right, we need find and choose a value of Last with maximum coin gained, and update the dp array. Our Answer is the value at dp[1][N].

Burst Balloon to maximize coins.cpp
content_copyfile_download
//https://www.geeksforgeeks.org/burst-balloon-to-maximize-coins/
#include <iostream>
using namespace std;

void burst (int arr[],int n) {
    int a[n+2];
    a[0]= 1, a[n+1]=1;
    for (int i=1;i<=n;i++)
        a[i]= arr[i-1];
    int dp[n+2][n+2];
    for (int i=0;i<n+2;i++)
        for (int j=0;j<n+2;j++)
            dp[i][j]=0;
    for (int length= 1; length<n+1; length++) {
        for (int left=1; left< n-length+2; left++) {
            int right= left+length-1;
            for (int last= left; last<right+1;last++)
                dp[left][right]= max(dp[left][right], dp[left][last-1]+a[left-1]*a[last]*a[right+1]+dp[last+1][right]);
        }
    }
    cout<< dp[1][n];
}


int main() {
    int n;
    cin>>n;
    int arr[n];
    for (int i=0;i<n;i++)
        cin>>arr[i];

    burst (arr,n);
}