Problem Description: We are given a stick of length N and a CUTS array of size C. The stick has markings as shown, and the CUTS array depicts the marking at which the stick needs to be cut (shown in red).
Note: It is necessary to make cuts at all the red markings.
Whenever we make a cut, we incur a cost. This cost is equal to the length of the stick on which we are making the cut.
We need to find the minimum cost incurred to cut the stick at all the cut points.
Examples
Here 16 is the minimum cost that can be incurred for the given CUTS array.
Expand any one approach by clicking the given options in the bar. Clicking one approach on bar,
closes all other expands. You can manually expand more than one approach at a time
Recursive Approach
Algorithm / Intuition
Intuition:
We need to minimize the cost incurred to cut the stick. Whenever we make a cut, we are changing the length of the stick which in turn decides the cost. Therefore the order in which we make the cuts changes the total cost. As discussed in DP-48 whenever the order of solving the problem comes into play, we can think in terms of Partition DP.
Let us quickly revise the rules to solve a problem on partition dp.
Start with the entire block/array and mark it with i,j.
Try all partitions.
Return the best possible answer of the two partitions (the answer that comes after dividing the problem into two subproblems and solving them recursively).
Now let us go through these rules and apply them one by one to the MCM problem.
Marking the array with i,j
We are given a stick of size N and the CUTS array. Every element of the CUTS array represents the marking at which one cut needs to be made. When we make a cut, we are dividing the stick into two different parts.
Ideally, we would want to place the i, and j pointers at both ends of the CUTS array and try to solve the problem recursively, which we will eventually do. But we need to modify the given array. We will first discuss the need for a modification and then we will learn about the exact modification required.
We have the following example:
Now, we try to place i and j on both ends of the CUTS array. Suppose we want to cut the stick at CUTS[0], i.e marking 3, then we will divide the bigger problem ( stick of length 7) into two smaller problems ( sticks of length 3 and 4) and solve these sub-problems independently (as we are looking for a recursive solution). Now the problem which arises is that when we make a cut at marking 3, we also need to think of something to distribute the CUTS array. This means we need to define separate i, and j pointers for each subproblem. We can try breaking the CUTS array in the following way:
Now the problem that we face here is that the information that marking 1 can be cut is not passed into the correct CUTS array of the left subproblem rather it is lying in the CUTS array of the right subproblem. Therefore these subproblems cannot be solved independently, thus defeating the whole point of a recursive solution. In order to solve this problem, we can initially sort the CUTS array. By sorting the CUTS array, we know that at whatever point we are making the cut, the information on the markings of the left portion will always be present on the left side of the CUTS array partition. Similarly on the right side.
Try all Partitions
As we have figured out the logic for marking the i, and j pointers, we will move to the partitioning loop. We can simply write a for loop(say ind) starting from i to j, The problem is being broken in the following manner:
Note: We are breaking the left subproblem to f(i,ind-1) rather than f(i,ind) because we have already made a cut at CUTS[ind] and we don’t want to consider it twice.
Base Case: As i <=j, we can say that when i>j this is not a valid partition so we can return 0.
Return the best possible answer to the two partitions:
We know that the recursive functions along with the base case will get us the answer to the subproblems, but still, there is some work to do. We need to find the cost incurred to make the cut that is breaking the stick at CUTS[ind]. The cost incurred will be the length of the stick on which the cut is being made. We only have the CUTS array to figure it out, let’s see how.
If we push 0 and N to both ends of the CUTS array:
Then CUTS[j+1] – CUTS[i-1] will always give us the correct length of the stick on which the cut is being made. Readers are advised to dry run with some other examples too to understand this.
Approach:
To summarize:
Sort the CUTS array.
Append 0 and N at both ends of the CUTS array.
Convert the problem to a recursive function marked by two pointers i and j.
Use a partitioning loop to try all partitions.
Return the answer in which the partition gives the minimum cost.
Code
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the minimum cost incurred
int findMinimumCost(int i, int j, vector<int> &cuts) {
// Base case: If i is greater than j, there are no cuts to consider.
if (i > j) {
return 0;
}
int mini = INT_MAX;
for (int ind = i; ind <= j; ind++) {
// Calculate the cost for making a cut at position 'ind'.
int ans = cuts[j + 1] - cuts[i - 1] +
findMinimumCost(i, ind - 1, cuts) +
findMinimumCost(ind + 1, j, cuts);
mini = min(mini, ans);
}
return mini;
}
// Function to compute the minimum cost
int minimumCost(int n, int c, vector<int> &cuts) {
// Modify the cuts array by adding 0 at the beginning and 'n' at the end.
cuts.push_back(n);
cuts.insert(cuts.begin(), 0);
sort(cuts.begin(), cuts.end());
// Call the recursive function to find the minimum cost.
return findMinimumCost(1, c, cuts);
}
int main() {
vector<int> cuts = {3, 5, 1, 4};
int c = cuts.size();
int n = 7;
cout << "The minimum cost incurred is: " << minimumCost(n, c, cuts) << endl;
return 0;
}
import java.util.*;
public class TUF {
// Recursive function to calculate the minimum cost
static int f(int i, int j, ArrayList<Integer> cuts) {
// Base case
if (i > j) {
return 0;
}
int mini = Integer.MAX_VALUE;
for (int ind = i; ind <= j; ind++) {
int ans = cuts.get(j + 1) - cuts.get(i - 1) +
f(i, ind - 1, cuts) +
f(ind + 1, j, cuts);
mini = Math.min(mini, ans);
}
return mini;
}
// Function to calculate the minimum cost
static int cost(int n, int c, ArrayList<Integer> cuts) {
// Modify the cuts array
cuts.add(n);
cuts.add(0);
Collections.sort(cuts);
return f(1, c, cuts);
}
public static void main(String[] args) {
ArrayList<Integer> cuts = new ArrayList<>(Arrays.asList(3, 5, 1, 4));
int c = cuts.size();
int n = 7;
System.out.println("The minimum cost incurred: " + cost(n, c, cuts));
}
}
def min_cost(n, c, cuts):
# Define a 2D memoization table to store intermediate results
dp = [[0] * (c + 2) for _ in range(c + 2)]
# Extend the cuts list with 0 and n, and sort it
cuts = [0] + cuts + [n]
cuts.sort()
# Fill the memoization table using dynamic programming
for length in range(2, c + 3):
for i in range(c + 3 - length):
j = i + length - 1
dp[i][j] = float('inf')
# Find the optimal partition point and calculate the cost
for k in range(i + 1, j):
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + (cuts[j] - cuts[i]))
# The result is stored in the top-right corner of the memoization table
return dp[0][c + 1]
if __name__ == "__main__":
cuts = [3, 5, 1, 4]
c = len(cuts)
n = 7
print("The minimum cost incurred:", min_cost(n, c, cuts))
function minimumCost(n, c, cuts) {
// Modify the cuts array
cuts.push(n);
cuts.unshift(0);
cuts.sort((a, b) => a - b);
// Create a 2D DP array to store the minimum cost
const dp = new Array(c + 2).fill(null).map(() => new Array(c + 2).fill(0));
// Calculate the minimum cost using dynamic programming
for (let chainSize = 2; chainSize <= c + 1; chainSize++) {
for (let i = 0; i < c + 2 - chainSize; i++) {
const j = i + chainSize - 1;
dp[i][j] = Infinity;
// Partitioning loop to find the minimum cost
for (let k = i + 1; k < j; k++) {
const cost = cuts[j] - cuts[i] + dp[i][k] + dp[k][j];
dp[i][j] = Math.min(dp[i][j], cost);
}
}
}
// The result will be stored in dp[0][c + 1], which represents the minimum cost
return dp[0][c + 1];
}
// Main function
function main() {
const cuts = [3, 5, 1, 4];
const c = cuts.length;
const n = 7;
const result = minimumCost(n, c, cuts);
console.log("The minimum cost incurred:", result);
}
// Call the main function
main();
The minimum cost incurred: 16
Complexity Analysis
Time Complexity: Exponential
Memoization Approach
Algorithm / Intuition
Steps to memoize the recursive solution:
Create a dp array of size [c+1][c+1]. i and j can range from 0 to c so we take the size c X c.
We initialize the dp array to -1.
Whenever we want to find the answer to particular parameters (say f(i,j)), we first check whether the answer is already calculated using the dp array(i.e dp[i][j]!= -1 ). If yes, simply return the value from the dp array.
If not, then we are finding the answer for the given value for the first time, we will use the recursive relation as usual but before returning from the function, we will set dp[i][j] to the solution we get.
Code
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the minimum cost incurred
int findMinimumCost(int i, int j, vector<int> &cuts, vector<vector<int>> &dp) {
// Base case: If i is greater than j, there are no cuts to consider.
if (i > j) {
return 0;
}
if (dp[i][j] != -1) {
return dp[i][j];
}
int mini = INT_MAX;
for (int ind = i; ind <= j; ind++) {
// Calculate the cost for making a cut at position 'ind'.
int ans = cuts[j + 1] - cuts[i - 1] +
findMinimumCost(i, ind - 1, cuts, dp) +
findMinimumCost(ind + 1, j, cuts, dp);
mini = min(mini, ans);
}
return dp[i][j] = mini;
}
// Function to compute the minimum cost
int minimumCost(int n, int c, vector<int> &cuts) {
// Modify the cuts array by adding 0 at the beginning and 'n' at the end.
cuts.push_back(n);
cuts.insert(cuts.begin(), 0);
sort(cuts.begin(), cuts.end());
// Create a DP table to store calculated values.
vector<vector<int>> dp(c + 1, vector<int>(c + 1, -1));
// Call the recursive function to find the minimum cost.
return findMinimumCost(1, c, cuts, dp);
}
int main() {
vector<int> cuts = {3, 5, 1, 4};
int c = cuts.size();
int n = 7;
cout << "The minimum cost incurred is: " << minimumCost(n, c, cuts) << endl;
return 0;
}
import java.util.*;
public class TUF {
// Recursive function to calculate the minimum cost
static int f(int i, int j, ArrayList<Integer> cuts, int[][] dp) {
// Base case
if (i > j) {
return 0;
}
if (dp[i][j] != -1) {
return dp[i][j];
}
int mini = Integer.MAX_VALUE;
for (int ind = i; ind <= j; ind++) {
int ans = cuts.get(j + 1) - cuts.get(i - 1) +
f(i, ind - 1, cuts, dp) +
f(ind + 1, j, cuts, dp);
mini = Math.min(mini, ans);
}
return dp[i][j] = mini;
}
// Function to calculate the minimum cost
static int cost(int n, int c, ArrayList<Integer> cuts) {
// Modify the cuts array
cuts.add(n);
cuts.add(0);
Collections.sort(cuts);
int[][] dp = new int[c + 1][c + 1];
for (int[] row : dp) {
Arrays.fill(row, -1);
}
return f(1, c, cuts, dp);
}
public static void main(String[] args) {
ArrayList<Integer> cuts = new ArrayList<>(Arrays.asList(3, 5, 1, 4));
int c = cuts.size();
int n = 7;
System.out.println("The minimum cost incurred: " + cost(n, c, cuts));
}
}
def min_cost(n, c, cuts):
# Define a 2D memoization table to store intermediate results
dp = [[-1] * (c + 1) for _ in range(c + 1)]
# Extend the cuts list with 0 and n, and sort it
cuts = [0] + cuts + [n]
cuts.sort()
# Recursive function to find the minimum cost
def f(i, j):
# Base case
if i > j:
return 0
if dp[i][j] != -1:
return dp[i][j]
mini = float('inf')
for ind in range(i, j + 1):
ans = cuts[j + 1] - cuts[i - 1] + f(i, ind - 1) + f(ind + 1, j)
mini = min(mini, ans)
dp[i][j] = mini
return mini
return f(1, c)
if __name__ == "__main__":
cuts = [3, 5, 1, 4]
c = len(cuts)
n = 7
print("The minimum cost incurred:", min_cost(n, c, cuts))
function minimumCost(n, c, cuts) {
// Modify the cuts array
cuts.push(n);
cuts.unshift(0);
cuts.sort((a, b) => a - b);
// Create a 2D DP array to store the minimum cost
const dp = new Array(c + 2).fill(null).map(() => new Array(c + 2).fill(-1));
// Recursive function to find the minimum cost
function f(i, j) {
// Base case
if (i > j) {
return 0;
}
// Check if the result is already computed
if (dp[i][j] !== -1) {
return dp[i][j];
}
let mini = Infinity;
// Partitioning loop to find the minimum cost
for (let ind = i; ind <= j; ind++) {
const ans =
cuts[j + 1] - cuts[i - 1] + f(i, ind - 1) + f(ind + 1, j);
mini = Math.min(mini, ans);
}
// Store the computed result and return
dp[i][j] = mini;
return mini;
}
// Call the recursive function to find the minimum cost
const result = f(1, c);
return result;
}
// Main function
function main() {
const cuts = [3, 5, 1, 4];
const c = cuts.length;
const n = 7;
const result = minimumCost(n, c, cuts);
console.log("The minimum cost incurred:", result);
}
// Call the main function
main();
The minimum cost incurred: 16
Complexity Analysis
Time Complexity: O(N*N*N)
Reason: There are 2 variables i and j, therefore, N*N states and we explicitly run a loop inside the function which will run for N times, therefore at max ‘N*N*N’ new problems will be solved.
Space Complexity: O(N*N) + O(N)
Reason: We are using an auxiliary recursion stack space(O(N))and a 2D array ( O(N*N)).
Tabulation Approach
Algorithm / Intuition
Tabulation:
First of all, we handle the base case. If (i > j) we return 0. To cover this case we can initialize the entire dp array with 0.
Next, memoization is a top-down approach, whereas tabulation is bottom-up. Our changing parameters i and j will change in opposite directions, i.e i will change from c→1 and j will change from 1→ c.
Next, we copy down the recursive logic inside the nested loops.
Code
#include <bits/stdc++.h>
using namespace std;
// Function to compute the minimum cost incurred
int minimumCost(int n, int c, vector<int> &cuts) {
// Modify the cuts array by adding 0 at the beginning and 'n' at the end.
cuts.push_back(n);
cuts.insert(cuts.begin(), 0);
sort(cuts.begin(), cuts.end());
// Create a DP table to store calculated values.
vector<vector<int>> dp(c + 2, vector<int>(c + 2, 0));
for (int i = c; i >= 1; i--) {
for (int j = 1; j <= c; j++) {
if (i > j) continue;
int mini = INT_MAX;
for (int ind = i; ind <= j; ind++) {
// Calculate the cost for making a cut at position 'ind'.
int ans = cuts[j + 1] - cuts[i - 1] + dp[i][ind - 1] + dp[ind + 1][j];
mini = min(mini, ans);
}
dp[i][j] = mini;
}
}
return dp[1][c];
}
int main() {
vector<int> cuts = {3, 5, 1, 4};
int c = cuts.size();
int n = 7;
cout << "The minimum cost incurred is: " << minimumCost(n, c, cuts) << endl;
return 0;
}
import java.util.*;
public class TUF {
// Function to calculate the minimum cost
static int cost(int n, int c, ArrayList<Integer> cuts) {
// Modify the cuts array
cuts.add(n);
cuts.add(0);
Collections.sort(cuts);
int[][] dp = new int[c + 2][c + 2];
for (int[] row : dp) {
Arrays.fill(row, 0);
}
for (int i = c; i >= 1; i--) {
for (int j = 1; j <= c; j++) {
if (i > j) continue;
int mini = Integer.MAX_VALUE;
for (int ind = i; ind <= j; ind++) {
int ans = cuts.get(j + 1) - cuts.get(i - 1) + dp[i][ind - 1] + dp[ind + 1][j];
mini = Math.min(mini, ans);
}
dp[i][j] = mini;
}
}
return dp[1][c];
}
public static void main(String[] args) {
ArrayList<Integer> cuts = new ArrayList<>(Arrays.asList(3, 5, 1, 4));
int c = cuts.size();
int n = 7;
System.out.println("The minimum cost incurred: " + cost(n, c, cuts));
}
}
def min_cost(n, c, cuts):
# Extend the cuts list with 0 and n, and sort it
cuts = [0] + cuts + [n]
cuts.sort()
# Create a 2D DP table initialized with zeros
dp = [[0] * (c + 2) for _ in range(c + 2)]
# Calculate the minimum cost using dynamic programming
for i in range(c, 0, -1):
for j in range(1, c + 1):
if i > j:
continue
mini = float('inf')
for ind in range(i, j + 1):
ans = cuts[j + 1] - cuts[i - 1] + dp[i][ind - 1] + dp[ind + 1][j]
mini = min(mini, ans)
dp[i][j] = mini
return dp[1][c]
if __name__ == "__main__":
cuts = [3, 5, 1, 4]
c = len(cuts)
n = 7
print("The minimum cost incurred:", min_cost(n, c, cuts))
function findMinimumCost(n, c, cuts) {
// Add the endpoints 0 and n to the cuts array and sort it
cuts.push(n);
cuts.unshift(0);
cuts.sort((a, b) => a - b);
// Create a 2D array dp to store the dynamic programming results
let dp = [];
for (let i = 0; i <= c + 1; i++) {
dp.push(new Array(c + 2).fill(0));
}
// Loop to fill in the dp array
for (let i = c; i >= 1; i--) {
for (let j = 1; j <= c; j++) {
// Skip invalid cases where i is greater than j
if (i > j) continue;
let mini = Infinity;
// Calculate the cost for each possible cut between i and j
for (let ind = i; ind <= j; ind++) {
let ans = cuts[j + 1] - cuts[i - 1] + dp[i][ind - 1] + dp[ind + 1][j];
mini = Math.min(mini, ans);
}
// Store the minimum cost in dp[i][j]
dp[i][j] = mini;
}
}
// The minimum cost is stored in dp[1][c]
return dp[1][c];
}
// Define the input values
let cuts = [3, 5, 1, 4];
let c = cuts.length;
let n = 7;
// Call the function and print the result
console.log("The minimum cost incurred:", findMinimumCost(n, c, cuts));
The minimum cost incurred: 16
Complexity Analysis
Time Complexity: O(N*N*N)
Reason: There are 2 variables i and j, therefore, N*N states and we explicitly run a loop inside the function which will run for N times, therefore at max ‘N*N*N’ new problems will be solved.
Space Complexity: O(N*N)
Reason: We are using a 2D array ( O(N*N)).
Video Explanation
Special thanks to Anshuman Sharma for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article. If you want to suggest any improvement/correction in this article please mail us at [email protected]
