Burst Balloons Solutions in C++

// Source : https://leetcode.com/problems/burst-balloons/
// Author : Hao Chen
// Date   : 2016-01-17





class Solution {
public:
    int maxCoins(vector<int>& nums) {
        //remove all of zero item
        nums.erase(remove_if(nums.begin(), nums.end(), [](int n){return n==0;}), nums.end());
        
        //add 1 for head and tail
        nums.insert(nums.begin(),1);
        nums.push_back(1);
        
        int n = nums.size();
        vector< vector<int> > matrix(n, vector<int>(n,0));
        
        return maxCoins_DP(nums, matrix);
        return maxCoins_DC(nums, matrix, 0, n-1);
    }
    
    
    //Divide and Conquer
    //
    //  If we seprate the array to two part, left part and right part.
    //
    //  Then, we will find in this problem the left and right become adjacent 
    //  and have effects on the maxCoins in the future.
    //
    //  So, if we think reversely, if the balloon i is the last balloon of all to burst, 
    //  the left and right section now has well defined boundary and do not affect each other! 
    //  Therefore we can do either recursive method with memoization
    //
    int maxCoins_DC(vector<int>& nums, vector<vector<int>>& matrix, int low, int high) {
        if (low + 1 == high) return 0;
        if (matrix[low][high] > 0) return matrix[low][high];
        int result = 0;
        for (int i = low + 1; i < high; ++i){
            result = max(result,  nums[low] * nums[i] * nums[high] 
                                    + maxCoins_DC(nums, matrix, low, i) 
                                    + maxCoins_DC(nums, matrix, i, high));
        }
        matrix[low][high] = result;
        return result;
    }
    
    //Dynamic Programming
    // 
    //  using the same idea of above 
    //
    int maxCoins_DP(vector<int>& nums, vector<vector<int>>& dp) {
        int n = nums.size();
        for (int k = 2; k < n; ++k) {
            for (int low = 0; low < n - k; low++){
                int high = low + k;
                for (int i = low + 1; i < high; ++i)
                    dp[low][high] = max( dp[low][high],
                         nums[low] * nums[i] * nums[high] + dp[low][i] + dp[i][high]);
            }
        }
        return dp[0][n - 1];
    }
    
private:
    void printVector(vector<int>& nums) {
        cout << "nums: ";
        for (auto n: nums) {
            cout << n << ' ';
        }
        cout << '\n';
    }
};

/// Source : https://leetcode.com/problems/burst-balloons/
/// Author : liuyubobobo
/// Time   : 2020-05-08

#include <iostream>
#include <vector>

using namespace std;


/// Memory Search
/// Time Complexity: O(n^3)
/// Space Complexity: O(n^2)
class Solution {
public:
    int maxCoins(vector<int>& nums) {

        nums.insert(nums.begin(), 1);
        nums.push_back(1);

        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(n, -1));
        return dfs(nums, 0, n - 1, dp);
    }

private:
    int dfs(const vector<int>& nums, int l, int r, vector<vector<int>>& dp){

        if(l == r) return dp[l][r] = 0;
        if(dp[l][r] != -1) return dp[l][r];

        int res = 0;
        for(int k = l + 1; k <= r - 1; k ++)
            res = max(res, dfs(nums, l, k, dp) + dfs(nums, k, r, dp) + nums[l] * nums[k] * nums[r]);
        return dp[l][r] = res;
    }
};


int main() {

    vector<int> nums = {3,1,5,8};
    cout << Solution().maxCoins(nums) << endl;
    // 167

    return 0;
}

/// Source : https://leetcode.com/problems/burst-balloons/
/// Author : liuyubobobo
/// Time   : 2020-05-08

#include <iostream>
#include <vector>

using namespace std;


/// Dynamic Programming
/// Time Complexity: O(n^3)
/// Space Complexity: O(n^2)
class Solution {
public:
    int maxCoins(vector<int>& nums) {

        nums.insert(nums.begin(), 1);
        nums.push_back(1);

        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));

        for(int len = 2; len < n; len ++)
            for(int start = 0; start + len < n; start ++)
                for(int k = start + 1; k < start + len; k ++)
                    dp[start][start + len] = max(dp[start][start + len],
                                                 dp[start][k] + dp[k][start + len] + nums[start] * nums[k] * nums[start + len]);
        return dp[0][n - 1];
    }
};


int main() {

    vector<int> nums = {3,1,5,8};
    cout << Solution().maxCoins(nums) << endl;
    // 167

    return 0;
}