[c++] dp 28ms solution
We define window size as gap in the code, representing the value of right-left. We also define dp as a 2d vector, dp[left][right] is the max cost of arr[left]*a
We define window size as `gap` in the code, representing the value of `right-left`. We also define dp as a 2d vector, `dp[left][right]` is the max cost of `arr[left]*arr[mid]*arr[right]` where `mid` goes from `left+1` to `right-1`. `dp[0][len-1]` is the returned value.\n\nFor example, given `nums` as {1,6,4,2,9}, if we select `1` and `9` as left and right index, `4` as middle index, max cost is `1*4*9 + dp[0][2] + dp[2][4]`.\n\nFirst we loop over `gap` from `2` to `len-1`. Given `gap`, we loop over `left` from `0` to `len-gap`. Given `gap` and `left`, `right` is just `left+gap`. Then we loop over `mid` from `left+1` to `right-1`. For each `mid`, `cur` is defined as `dp[left][mid]+dp[mid][right]+arr[left]*arr[mid]*arr[right]`. We assign the max value of `cur` to `dp[left][right]`.\n\n**If it helps, plz upvote!**\n\n```\nclass Solution {\npublic:\n    int maxCoins(vector<int>& nums) {\n        int n = nums.size();\n        int len = n+2;\n        vector<int> arr = {1};\n        for(auto& num : nums)\n            arr.push_back(num);\n        arr.push_back(1);\n        \n        vector<vector<int>> dp(len, vector<int>(len, 0));\n        \n        for(int gap = 2; gap < len; gap++) {\n            for(int left = 0; left < len-gap; left++) {\n                int right = left+gap;\n                int cur = 0;\n                for(int mid = left+1; mid < right; mid++) {\n                    cur = max(cur, dp[left][mid]+dp[mid][right]+arr[left]*arr[mid]*arr[right]);\n                }\n                dp[left][right] = cur;\n            }\n        }\n        return dp[0][len-1];\n    }\n};\n//IO\nint _IO=[](){\n\tios::sync_with_stdio(0);\n\tcin.tie(0); //cout.tie(0);\n\treturn 0;\n}();\n```
['Divide and Conquer', 'Dynamic Programming', 'C']