Monday, January 4, 2016

LeetCode OJ - Burst Balloons

Problem: 

Please find the problem here.

Solution:

I learn this new idea of interval dynamic programming. As of any dynamic programming, the key idea is to find out what are the sub-problems.

Originally, I was struggled after picking the first one to burst, bursting the leftmost balloon on the right hand side is going to have impact on the left hand side sub-problem, so we have many sub-problems, not good.

The key idea is, instead of picking the first one to burst, pick the last one. The last one fix the boundary of the both sub-problems so we can divide and conquer.

In particular, define $ f[i,j] $ as the optimal number of coins one can collect in the closed interval $ [i, j] $ subject to the constraint that $ [i-1] $ and $ [j + 1] $ is not bursted until $ [i,j] $ is bursted.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/burst-balloons/

#include "LEET_BURST_BALLOONS.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>

using namespace std;

namespace _LEET_BURST_BALLOONS
{
    class Solution
    {
    public:
        int maxCoins(vector<int>& nums)
        {
            if (nums.size() == 0)
            {
                return 0;
            }

            // interval_solution[i][j] represents the maximum number of coins one can collect 
            // in the range [i, j] subject to the constraint that the (i-1)th and the (j+1)th 
            // balloon is not bursted until all balloons in [i, j] are bursted.
            vector<vector<int>> interval_solution;
            unsigned int n = nums.size();
            interval_solution.resize(n);
            for (unsigned int i = 0; i < n; i++)
            {
                interval_solution[i].resize(n);
            }

            // We build the solution from short interval to long ones
            for (int interval_length = 1; interval_length <= n; interval_length++)
            {
                int interval_src = 0;
                while (true)
                {
                    int interval_dst = interval_src + interval_length - 1; // the inclusive end index
                    if (interval_dst == n)
                    {
                        break;
                    }

                    int best = -1;
                    for (int last_balloon = interval_src; last_balloon <= interval_dst; last_balloon++)
                    {
                        // Since this is the last balloon to burst, all other balloons within the interval are bursted
                        // So at the time the last balloon is bursted, the last balloon is between the boundary of the interval
                        int last_balloon_prev_value = interval_src == 0 ? 1 : nums[interval_src - 1];
                        int last_balloon_next_value = interval_dst == n - 1 ? 1 : nums[interval_dst + 1];
                        int burst_value = last_balloon_prev_value * nums[last_balloon] * last_balloon_next_value;

                        // The total value of bursting all balloon is divided into three parts, the 
                        // portion before the last balloon, the last balloon itself, and the portion after the last balloon.
                        // In actual bursting, one could interleave bursting balloon is the left hand side or right hand side.
                        // The optimal bursting value is unchanged
                        int prev_value = last_balloon == interval_src ? 0 : interval_solution[interval_src][last_balloon - 1];
                        int next_value = last_balloon == interval_dst ? 0 : interval_solution[last_balloon + 1][interval_dst];

                        int total_value = prev_value + burst_value + next_value;

                        best = max(best, total_value);
                    }
                    interval_solution[interval_src][interval_dst] = best;

                    interval_src++;
                }
            }
            return interval_solution[0][n - 1];
        }
    };
};

using namespace _LEET_BURST_BALLOONS;

int LEET_BURST_BALLOONS()
{
    int case1[] = { 3, 1, 5, 8 };
    Solution solution;
    cout << solution.maxCoins(vector<int>(case1, case1 + _countof(case1))) << endl;
    return 0;
}

No comments :

Post a Comment