0312. Burst Balloons.md

312. Burst Balloons

https://leetcode.com/problems/burst-balloons/discuss/76245/Easiest-Java-Solution https://leetcode.com/problems/burst-balloons/discuss/232224/If-you-are-stuck-view-this-video!

class Solution {
    int get(const vector<int>& nums, int i) {
        if (i < 0 || i >= nums.size())
            return 1;
        return nums[i];
    }
    int check(const vector<int>& nums, int start, int end, vector<vector<int>>& dp ) {
        if (start > end) return 0;
        
        if (dp[start][end] > 0) {
            return dp[start][end];
        }
        int res = nums[start];
        // iterate assuming nums[i] will be bursted last
        for (int i = start; i <= end; i++) {
            int r = check(nums, start, i-1, dp) +
                       get(nums, start-1)*nums[i]*get(nums, end+1) +
                        check(nums, i+1, end, dp);
            res = max(res, r);
        }
        dp[start][end] = res;
        return res;
    }
public:
    int maxCoins(vector<int>& nums) {
        vector<vector<int>> dp(nums.size(), vector<int>(nums.size(), 0));
        
        return check(nums, 0, nums.size()-1, dp);
    }
};

class Solution {
    int get(const vector<int>& nums, int i) {
        if (i < 0 || i >= nums.size())
            return 1;
        return nums[i];
    }
public:
    int maxCoins(vector<int>& nums) {
        if (nums.empty()) return 0;
        
        vector<vector<int>> dp(nums.size(), vector<int>(nums.size(), 0));
        
        for (int i = 1; i <= nums.size(); i++) {
            for (int j = 0; j <= nums.size()-i; j++) {
                int start = j;
                int end = j + i - 1; // inclusive
                
                // assume nums[k] will be bursted last
                int res = 0;
                for (int k = start; k <= end; k++) {
                    int r = (k > 0? dp[start][k-1] : 0) +
                        get(nums, start-1)*nums[k]*get(nums, end+1) +
                        (k < nums.size()-1? dp[k+1][end] : 0);
                    res = max(res, r);
                }
                dp[start][end] = res; //max(res, dp[start][end]);
            }
        }
        return dp[0][nums.size()-1];
    }
};