C++  dp with/without recursion
cpp\n    int maxCoins(vector<int>& nums) {\n        nums.insert(nums.begin(), 1);\n        nums.push_back(1);\n        \n        vector<vector<int>> dp(nums.siz
```cpp\n    int maxCoins(vector<int>& nums) {\n        nums.insert(nums.begin(), 1);\n        nums.push_back(1);\n        \n        vector<vector<int>> dp(nums.size(), vector<int>(nums.size()));\n        \n        for (int len=1; len<nums.size()-1; len++) {\n            for (int i=1; i+len-1<nums.size()-1; i++) {\n                int s = 0;\n                for (int k=i; k<=i+len-1; k++)\n                    s = max(s, nums[i-1] * nums[k] * nums[i+len] + dp[i][k-1] + dp[k+1][i+len-1]);\n                dp[i][i+len-1] = s;\n            }\n        }\n        return dp[1][nums.size()-2];\n    }\n```\n\nWith recursion\n```cpp\n    int maxCoins(vector<int>& nums) {\n        nums.insert(nums.begin(), 1);\n        nums.push_back(1);\n        \n        vector<vector<int>> dp(nums.size(), vector<int>(nums.size(), -1));\n        \n        function<int(int,int)> calc = [&](int start, int end){\n            if (start > end) return 0;\n            if (dp[start][end] != -1) return dp[start][end];\n            int s = 0;\n            for (int i=start; i<=end; i++) {\n                int ss = nums[start-1] * nums[i] * nums[end+1] + calc(start, i-1) + calc(i+1, end);\n                s = max(ss, s);\n            }\n            dp[start][end] = s;\n            return s;\n        };\n        \n        return calc(1, nums.size()-2); \n    }\n```
[]