Share my both dp and divide conquer solutions


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

  • 0
    L

    Could you tell me ,what is the dp code?

     int temp = dp[i][x-1] + nums[i-1]*nums[x]*nums[j+1] + dp[x+1][j];
    

    thx !


  • 2
    C

    Your divide and conquer is also dynamic programming but top-down instead of bottom-up.


  • 0
    D

    @clark3 I agree. The divide and conquer shown above is another way of writing bottom-up dp, which is called memoization dp (from top-bottom).


Log in to reply
 

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