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
- merge first 4 and first 3, cost 7
- merge second 3 and second 4, cost 7
- merge two 7s, cost 14
- total cost = 7 + 7 + 14 = 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}
- nums = {3,1,5,8} –> {3,5,8} –> {3,8} –> {8} –> {}
- coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
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];
}