Recursion version DP
You should never worry about the loop sequence in recursion.\n\n    class Solution {\n    public:\n        int maxCoins(vector& nums) {\n            int n = num
You should never worry about the loop sequence in recursion.\n\n    class Solution {\n    public:\n        int maxCoins(vector<int>& nums) {\n            int n = nums.size();\n            vector<vector<int>> f(n + 1, vector<int>(n + 1, -1));\n            vector<int> nums1(n + 2, 1);\n            for (int i = 0; i < n; ++i) {\n                nums1[i + 1] = nums[i];\n            }\n            return search(nums1, f, 1, n);\n        }\n    private:\n        int search(const vector<int>& nums, vector<vector<int>>& f, const int i, const int j) {\n            if (i > j) {\n                return 0;\n            }\n            if (f[i][j] >= 0) {\n                return f[i][j];\n            }\n            for (int k = i; k <= j; ++k) {\n                f[i][j] = max(f[i][j], search(nums, f, i, k - 1) + search(nums, f, k + 1, j) + nums[k] * nums[i - 1] * nums[j + 1]);\n            }\n            return f[i][j];\n        }\n    };
[]