312. Burst Balloons

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the ith balloon, you will get nums[i - 1] nums[i] nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

Return the maximum coins you can collect by bursting the balloons wisely.

class Solution {
    vector<vector<int>> dp;
    int helper(vector<int>& nums, int l, int r) {
        if(l + 1 == r) return 0;
        if(dp[l][r] != -1) return dp[l][r];
        dp[l][r] = 0;
        for(int i = l + 1; i < r; i++) {
            dp[l][r] = max(
                dp[l][r],
                nums[l] * nums[i] * nums[r] +
                helper(nums,l,i) + helper(nums,i,r));
        }
        return dp[l][r];
    }
public:
    int maxCoins(vector<int>& nums) {
        vector<int> nonZeroNums(nums.size() + 2);
        int n = 1;
        for(auto num : nums) {
            if(num)
                nonZeroNums[n++] = num;
        }
        nonZeroNums[0] = nonZeroNums[n] = 1;
        dp = vector<vector<int>>(n + 1, vector<int>(n + 1, -1));
        return helper(nonZeroNums, 0, n);
    }
};