Thought Process To Come Up With The Solution
This blog made a lot of sense to me: \nIt explains how one can think of the solution from scratch.\n\n\nclass Solution {\npublic:\n    int maxCoins(vector<int>&
[This](https://medium.com/algorithms-digest/bursting-balloons-1820664a4ffa) blog made a lot of sense to me: \nIt explains how one can think of the solution from scratch.\n\n```\nclass Solution {\npublic:\n    int maxCoins(vector<int>& nums) {\n        \n        // Get the number of balloons\n        int n = nums.size();\n        \n        // Generate a new array by adding 1 on the left and right of nums[]\n        vector<int> numsDP(n+2);\n        numsDP[0] = numsDP[n+1] = 1;\n        for(int i=1; i<=n; i++)\n            numsDP[i] = nums[i-1];\n        \n        // Initialize entries of dp[][] with -1\n        int dp`[n+2][n+2];\n        for(int i=0; i<n+2; i++)\n            for(int j=0; j<n+2; j++)\n                dp[i][j] = -1;\n    \n        // Iterate over different subarray sizes (s) in a bottom-up manner\n        for(int s=2; s<=(n+2); s++)\n        {\n            for(int i=0; i<n+2-s+1; i++)\n            {\n                // Size 2 sub-arrays corespond to the base case (0 coins collected)\n                if(s == 2)\n                    dp[i][i+s-1] = 0;\n                else // For other sub-arrays use the recusive formulation\n                {\n                    // Consider all possible choices of the last balloon to be burst\n                    // And select the onee which maximises the number of coins collected\n                    for(int j=i+1; j<(i+s-1); j++)\n                    {\n                        dp[i][i+s-1] = max(dp[i][i+s-1], dp[i][j] + dp[j][i+s-1] + numsDP[i]*numsDP[j]*numsDP[i+s-1]);\n                    }\n                }\n            }\n        }\n        // Final answer is dp[0][n+1]\n        return dp[0][n+1];\n    }\n};\n```
[]