PINEAL.ME   Archives  About

Dynamic Programming I

Max Product Of Cutting Rope

Given a rope with positive integer-length n, how to cut the rope into m integer-length parts with length $p[0], p[1], …,p[m-1]$, in order to get the maximal product of $p[0]p[1] … p[m-1]$? m is determined by you and must be greater than 0 (at least one cut must be made). Return the max product you can have.

Example

n = 12, the max product is 3 * 3 * 3 * 3 = 81 (cut the rope into 4 pieces with length of each is 3).

Top-Down Recursion

int maxProduct(int length) {
    if (length <= 2) {
      return 1;
    }
    int res = 0;
    for (int i = 1; i < length - 1; i++) {
      res = max(res, max(length - i, maxProduct(length - i)) * i);
    }
    return res;
  }

Top-Down Recursion + Memorization

int maxProduct(int length) {
    if (length <= 2) {
      return 1;
    }
    vector<int> M(length + 1, 0);
    return maxProductHelper(length, M);
  }
  
  int maxProductHelper(int length, vector<int> & M) {
    if (M[length]) {
      return M[length];
    }
    int res = 0;
    for (int i = 1; i < length - 1; i++) {
      res = max(res, max(length - i, maxProductHelper(length - i, M)) * i);
    }
    M[length] = res;
    return res;
  }

Bottom-up DP Solution

int maxProduct(int length) {
    vector<int> M(length + 1, 0);
    //M[i] => max product of first i length rope
    for (int i = 1; i < length + 1; i++) {
      for (int j = 0; j < i; j++) {
        M[i] = max(M[i], max(j, M[j])/*take care of corner case*/ * (i - j));
      }
    }
    return M.back();
}

Cut rope II

There is a wooden stick with length L >= 1, we need to cut it into pieces, where the cutting positions are defined in an int array A. The positions are guaranteed to be in ascending order in the range of $[1, L - 1]$. The cost of each cut is the length of the stick segment being cut. Determine the minimum total cost to cut the stick into the defined pieces.

Top-Down Recursion

int minCost(vector<int> cuts, int length) {
    cuts.insert(cuts.begin(),0);
    cuts.emplace_back(length);
    return helper(0, cuts.size() - 1, cuts);
  }
  
  int helper(int start, int end, const vector<int> & cuts) {
    if (start + 1 == end) {
      return 0;
    }
 
    int res = INT_MAX;
    for (int k = start + 1; k < end; k++) {
      res = min(res, helper(start, k, cuts) + 
                cuts[end] - cuts [start] + 
                helper(k, end, cuts));
    }
    return res;
  }

Top-Down Recursion + Memorization

  int minCost(vector<int> cuts, int length) {
    cuts.insert(cuts.begin(),0);
    cuts.emplace_back(length);
    int n = cuts.size();
    vector<vector<int>> M(n, vector<int>(n, INT_MAX));
    return helper(0, n - 1, cuts, M);
  }

  int helper(int start, int end, const vector<int> & cuts, vector<vector<int>> & M) {
    if (start + 1 == end) {
      return 0;
    }
    if (M[start][end] != INT_MAX) {
      return M[start][end];
    } 
    int res = INT_MAX;
    for (int k = start + 1; k < end; k++) {
      res = min(res, helper(start, k, cuts, M) + 
                cuts[end] - cuts [start] + 
                helper(k, end, cuts, M));
    }
    M[start][end] = res;
    return res;
  }

Dynamic Programming

  int minCost(vector<int> cuts, int length) {
    cuts.insert(cuts.begin(),0);
    cuts.emplace_back(length);
    int n = cuts.size();
    vector<vector<int>> M(n, vector<int>(n, INT_MAX));
    for (int right = 1; right < n; right++) {
      for (int left = right - 1; left >= 0; left--) {
        if (left + 1 == right) {
          M[left][right] = 0;
        }
        else {
          for (int k = left + 1; k <= right - 1; k++) {
            M[left][right] = min(M[left][right],
                          M[left][k] + M[k][right] + cuts[right] - cuts[left]);            
          }
        }
      }
    }
    return M.front().back();
  }

Merge Stone

We have a list of piles of stones, each pile of stones has a certain weight, represented by an array of integers. In each move, we can merge two adjacent piles into one larger pile, the cost is the sum of the weights of the two piles. We merge the piles of stones until we have only one pile left. Determine the minimum total cost.

stones is not null and is length of at least 1

Example

{4, 3, 3, 4}, the minimum cost is 28

Recursion + memo

int minCost(vector<int> stones) {
    return helper(0, stones.size() - 1, stones);
  }
  
  int helper(int left, int right, const vector<int> & stones) {
    if (left == right) {
      return 0;
    }
    if (left + 1 == right) {
      return stones[left] + stones[right];
    }
    
    int sum = 0;
    for (int i = left; i <= right; i++) {
      sum += stones[i];
    }
    
    int res = INT_MAX;
    for (int k = left; k <= right - 1; k++) {
      res = min(res, 
                helper(left, k, stones) + helper(k + 1, right, stones) + sum);
    }
    return res;
  }

Dynamic Programming

int minCost(vector<int> stones) {
    int n = stones.size();
    //sum[i] ==> sum from stones[0] to stones[i]
    vector<int> sums(n);
    for (int i = 0; i < stones.size(); i++) {
      if (i == 0) {
        sums[i] = stones[i];
      }
      else {
        sums[i] = sums[i - 1] + stones[i];
      }
    }
    //M[i][j] => min cost from stones[i] to stones[j]
    vector<vector<int>> M(n, vector<int>(n, INT_MAX));
    for (int right = 0; right < n; right++) {
      for (int left = right; left >= 0; left--) {
        int sum = left == 0? sums[right] : sums[right] - sums[left - 1];
        if (left == right) {
          M[left][right] = 0;
          continue;
        }
        //k => last stone to merge
        for (int k = left; k <= right; k++) {
          int rightsub = k == right? 0 : M[k + 1][right];
          M[left][right] = min(M[left][right], 
                               M[left][k] + sum + (k == right? 0 : M[k + 1][right]));
        }
      }    
    }
    return M.front().back();
  }

Burst Bsllons

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get $nums[left] * nums[i] * nums[right]$ coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:

You may imagine $nums[-1] = nums[n] = 1$. They are not real therefore you can not burst them.

Example

Input: {3,1,5,8}

Recursion

  int maxCoins(vector<int>& nums) {
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        return helper(0, nums.size() - 1, nums);
    }
    
    int helper(int start, int end, vector<int> & nums) {
        if (start + 1 == end) {
            return 0;
        }
        int res = 0;
        for (int i = start + 1; i < end; i++) {
            res = max(res, 
                      helper(start, i, nums) + 
                      nums[start] * nums[i] * nums[end] + 
                      helper(i, end, nums));
        }
        return res;
    }

Recursion + Memo

  int maxCoins(vector<int>& nums) {
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        int n = nums.size();
        vector<vector<int>> M(n, vector<int>(n, 0));
        return helper(0, nums.size() - 1, nums, M);
    }
    
    int helper(int start, int end, const vector<int> & nums, vector<vector<int>> & M) {
        if (start + 1 == end) {
            return 0;
        }
        if (M[start][end]) {
            return M[start][end];
        }
        int res = 0;
        for (int i = start + 1; i < end; i++) {
            res = max(res, 
                      helper(start, i, nums, M) + 
                      nums[start] * nums[i] * nums[end] + 
                      helper(i, end, nums, M));
        }
        M[start][end] = res;
        return res;
    }

Dynamic Programming

  int maxCoins(vector<int>& nums) {
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        int n = nums.size();
        vector<vector<int>> M(n, vector<int>(n, 0));

        for (int right = 2; right < n; right++) {
            for (int left = right - 2; left >= 0; left--) {
                for (int k = left + 1; k < right; k++) {
                    M[left][right] = max(M[left][right],
                                        M[left][k] + nums[left] * nums[k] * nums[right] + M[k][right]);
                }
            }
        }
        return M[0][n - 1];
    }
Dynamic Programming