C++ dynamic programming, O(N^3), 32 ms, with comments
int maxCoins(vector<int>& nums) {\n        int N = nums.size();\n        nums.insert(nums.begin(), 1);\n        nums.insert(nums.end(), 1);\n    \n        // ra
    int maxCoins(vector<int>& nums) {\n        int N = nums.size();\n        nums.insert(nums.begin(), 1);\n        nums.insert(nums.end(), 1);\n    \n        // rangeValues[i][j] is the maximum # of coins that can be obtained\n        // by popping balloons only in the range [i,j]\n        vector<vector<int>> rangeValues(nums.size(), vector<int>(nums.size(), 0));\n        \n        // build up from shorter ranges to longer ranges\n        for (int len = 1; len <= N; ++len) {\n            for (int start = 1; start <= N - len + 1; ++start) {\n                int end = start + len - 1;\n                // calculate the max # of coins that can be obtained by\n                // popping balloons only in the range [start,end].\n                // consider all possible choices of final balloon to pop\n                int bestCoins = 0;\n                for (int final = start; final <= end; ++final) {\n                    int coins = rangeValues[start][final-1] + rangeValues[final+1][end]; // coins from popping subranges\n                    coins += nums[start-1] * nums[final] * nums[end+1]; // coins from final pop\n                    if (coins > bestCoins) bestCoins = coins;\n                }\n                rangeValues[start][end] = bestCoins;\n            }\n        }\n        return rangeValues[1][N];\n    }
[]