[recommend for beginners]clean C++ implementation with detailed explanation


  • 1
    class Solution {
    public:
        int maxCoins(vector<int>& nums) {
            vector<int> _nums(nums);
            _nums.insert(_nums.begin(), 1);
            _nums.push_back(1);
            int n=_nums.size();
            vector<vector<int>> matrix(n, vector<int>(n, 0));
            //return 0;
            return help(_nums, matrix, 0, n-1);
        }
        /*** (start, end)  ***/
        int help(vector<int>& nums, vector<vector<int>>& matrix, int low, int high){
            if(low+1==high)  return 0;
            if(matrix[low][high]>0)  return matrix[low][high];
            int result=0;
            for(int i=low+1; i<high; i++){
                result=max(result, nums[low]*nums[i]*nums[high],
                                   +help(nums, matrix, low, i)
                                   +help(nums, matrix, i, high));
            }
            matrix[low][high]=result;
            return result;
        }
    };

  • 2

    In the two end, we add 1 to make it more easy to code.

    The key is to make it clear to think about the equation. We can choose i in [start+1, end-1] as the last

    number and we choose the start and end as the open field of the problem.

    So the DFS solution is like this.

    The vector can insert number in the start position or any position by using the insert function.

    class Solution {
    public:
        int maxCoins(vector<int>& nums) {
            nums.insert(nums.begin(), 1);
            nums.push_back(1);
            
            int len=nums.size();
            vector<vector<int>> dp(len, vector<int>(len, 0));
            return help(nums, dp, 0, len-1);
        }
        
        /** (low, high) all is open field **/
        int help(vector<int>& nums, vector<vector<int>>& dp, int low, int high){
            if(low+1==high)  return 0;
            if(dp[low][high]>0)  return dp[low][high];
            int result=0;
            for(int i=low+1; i<high; i++){
                result=max(result, nums[low]*nums[i]*nums[high]
                                  + help(nums, dp, low, i)
                                  + help(nums, dp, i, high));
            }
            dp[low][high]=result;
            return result;
        }
    };
    

    Similar to the DFS solution, we can implement the DP based solution like this


  • 2
    class Solution {
    public:
        int maxCoins(vector<int>& nums) {
            if(nums.size()==0)  return 0;
            if(nums.size()==1)  return nums[0];
            nums.insert(nums.begin(), 1);
            nums.push_back(1);
            int len=nums.size();
            vector<vector<int>> dp(len, vector<int>(len, 0));
            /**
             *   dp[j][i]=max(dp[j][i], nums[i]*nums[j]*nums[k]+dp[j][k]+dp[k][i]);
             **/
             for(int i=2; i<len; i++){
                 for(int j=i-1; j>=0; j--){
                     for(int k=j+1; k<i; k++){
                         dp[j][i]=max(dp[j][i], nums[i]*nums[j]*nums[k]+dp[j][k]+dp[k][i]);
                     }
                 }
             }
             return dp[0][len-1];
        }
    };

  • 0

    This is the more concise DP solution. The important lesson I learned from here is that we should make clear the order of the DP solution loop. Based on different equation, we ensure the loop direction is correct.


  • 0
    2

    DFS & state memorization method .....


  • 1
    2

    DP solution for pratice

    class Solution {
    public:
        int maxCoins(vector<int>& nums) {
            int size_nums = nums.size();
            if(size_nums <= 0)  return 0;
            
            nums.insert(nums.begin(), 1);
            nums.push_back(1);
            
            size_nums = nums.size();
            vector<vector<int>> dp(size_nums, vector<int>(size_nums, 0));
            
            /**
             * dp[i][j] = max { dp[i][k] + dp[k][j] + nums[i]* nums[k] *nums[j] }
             **/
            for(int j = 2; j < size_nums; j++) {
                for(int i = j - 1; i >= 0; i--) {
                    /** k in (i, j) field **/
                    for(int k = i + 1; k < j; k ++) {
                        dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]);
                    }
                }
            }
            
            return dp[0][size_nums-1];
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.