My C++ recursive solution with detailed explanation.
class Solution {\n    public:\n        int maxCoins(vector<int>& nums) {\n            // preprocessing: remove all zeros, insert 1 into the begin and the end\n 
    class Solution {\n    public:\n        int maxCoins(vector<int>& nums) {\n            // preprocessing: remove all zeros, insert 1 into the begin and the end\n            vector<int> cleaned = {1};\n            for (auto &num : nums)\n                if (num) cleaned.push_back(num);\n            cleaned.push_back(1);\n\n            int n = cleaned.size()-2;\n            // dp[start][end] means the max score we can get from bursting [start, end] balloons.\n            vector<vector<int>> dp(n+1, vector<int>(n+1, -1));\n\n            return maxCoins(1, n, cleaned, dp);\n        }\n    private:\n        // the real workhorse\n        int maxCoins(int start, int end, vector<int> &nums, vector<vector<int>> &dp) {\n            // empty\n            if (start>end) return 0;\n\n            // if the result is ready, return it directly.\n            if (dp[start][end]!=-1)\n                return dp[start][end];\n\n            // the boundary of recursion.\n            if (start == end) {\n                dp[start][end] = nums[start-1]*nums[start]*nums[start+1];\n                return dp[start][end];\n            }\n\n            /**\n             *\n             * max score of [start, end] can be obtained as follow:\n             * let lastBurst point to the last balloon to be bursted,\n             * the score is the sum of:\n             *  1. left part to the lastBurst, i.e, [start, lastBurst-1]\n             *  2. the score of nums[start-1], nums[lastBurst], nums[end+1],\n             *     since all the balloons in [start, lastBurst-1] and [lastBurst+1, end] are bursted.\n             *  3. right part from the lastBurst, i.e, [lastBurst+1, end]\n             * Just iterate lastBurst from start to end to calculate the max score of [start, end]\n             *\n             */\n            for (int lastBurst=start; lastBurst<=end; ++lastBurst) {\n                dp[start][end] = max(dp[start][end],\n                                    nums[start-1]*nums[lastBurst]*nums[end+1] +\n                                        maxCoins(start, lastBurst-1, nums, dp) +\n                                        maxCoins(lastBurst+1, end, nums, dp));\n            }\n            return dp[start][end];\n        }\n    };
['Dynamic Programming', 'Recursion']