Share my both dp and divide conquer solutions
// dp solution\n    // dp[i][j] = max(dp[i][j], dp[i][x-1] + nums[i-1]*nums[x]*nums[j+1] + dp[x+1][j]; // x from i to j\n    int maxCoins(vector<int>& nums) {\n
    // dp solution\n    // dp[i][j] = max(dp[i][j], dp[i][x-1] + nums[i-1]*nums[x]*nums[j+1] + dp[x+1][j]; // x from i to j\n    int maxCoins(vector<int>& nums) {\n        int n = nums.size();\n        nums.insert(nums.begin(), 1);\n        nums.insert(nums.end(), 1);\n        \n        vector<vector<int> > dp(n+2, vector<int>(n+2, 0));\n\n        // k indetify the the body length for dp[i, j]\n        // travel all the possibility for body length for 1 to n    \n        for (int k = 1; k <= n; k++) { \n                // [i, j] body length from 1 to n\n                for (int i = 1; i <= n - k + 1; ++i) {\n                int j = i + k - 1;\n                // x between [i, j]                    \n                for (int x = i; x <= j; ++x) {\n                    int temp = dp[i][x-1] + nums[i-1]*nums[x]*nums[j+1] + dp[x+1][j];\n                    if (temp > dp[i][j]) dp[i][j] = temp;\n                }\n            }\n        }\n        \n        return dp[1][n];\n    }\n\n    // divide and conquer\n    int maxCoins1(vector<int>& nums) {\n        int n = nums.size();\n        nums.insert(nums.begin(), 1);\n        nums.insert(nums.end(), 1);\n        vector<vector<int> > dp(n+2, vector<int>(n+2, 0));\n        return DP(1, n, nums, dp);\n    }\n    \n    // remember search\n    int DP(int i, int j, const vector<int> &nums, vector<vector<int>> &dp) {\n        if (dp[i][j] > 0) return dp[i][j];\n        for (int x = i; x <= j; ++x) {\n            int temp = DP(i, x-1, nums, dp) + nums[i-1]*nums[x]*nums[j+1] + DP(x+1, j, nums, dp);\n            if (temp > dp[i][j]) dp[i][j] = temp;\n        }\n        return dp[i][j];\n    }
[]