Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach1 - Brute Force - Using Recursion
3.1.
Implementation
3.2.
Complexity Analysis
4.
Approach 2 - Using Dynamic Programming
4.1.
APPROACH 2a: Via using Unbounded Knapsack
4.1.1.
Implementation
4.1.2.
Complexity Analysis
4.2.
APPROACH 2b: Optimised Approach
4.2.1.
Implementation
4.2.2.
Complexity Analysis
5.
Frequently Asked Questions
5.1.
What is dynamic programming?
5.2.
What are two ways to apply dynamic programming?
5.3.
What is the best case time complexity for the Rod Cutting Problem?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Rod Cutting Problem

Author Raksha Jain
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Today, let’s learn about a famous and commonly asked Interview Problem, i.e., Rod Cutting Problem. 

It is a famous and common problem of data structure that is solved using Dynamic Programming in its most optimized version.  

Problem Statement

Given a rod of length n and a price array that includes prices of all pieces of rod smaller than N, determine the maximum profit obtained from cutting the rod into pieces and selling it.

Example: 

 

length   | 1   2   3   4   5   6   7   8  

--------------------------------------------

price    | 1   5   8   9  10  17  17  20

 

Here, the length of the entire rod = 8 units.

So, we can divide the entire rod into multiple fashions like 

 

Profit Earned

Selling the entire rod together as a single unit (of length 8) 1 piece *  price[8] = Rs. 20

Cutting the entire length of rod into 1 unit length  8 pieces * price[1] = Rs. 8

Cutting the rod into 3 units + 5 units length              price[3] + price[5] =  8  + 10 = Rs. 18

Cutting the rod into 2 units + 6 units length            price[2] + price[6] =  5  +  17 = Rs. 22  

 

and so on. 

We will notice that the max profit that could be generated is Rs. 22. 

 

Let's get started and learn various approaches to solve this problem. 

 

gif

Note: Before stepping toward the solution, try to solve Rod Cutting Problem by yourself on Coding Ninjas Studio.

Approach1 - Brute Force - Using Recursion

The naive (or brute force) solution of this problem could be finding all possible configurations of different pieces and finding the highest profit possible configuration. 

   Cut ith length Subproblem.Rod Cut

 

So, cut ith length rod, store its price and calculate the price for the rest of the rod’s length via Recursion.

=> Profit Earned = price[i] + f(N  -  cut)

 

=> f(N) = max of {

    

          1

Rod cutprice[0] + f(N  -  1)

 

           2

Rod Cutprice[1] + f(N  -  2)

 

             3

Rod Cutprice[2] + f(N  -  3)

.

.

.

.

.

             n

Rod Cutprice[n  -  1] + 0

}

 

=> Max profit earned = max(price[i] + f(n - cut))  where i = 0 to n - 1 (n = length of rod)

 

Note: The base case would be that if (n = 0) profit earned would be 0. 

Implementation

Let’s have a look at its implementation in Java. 

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Solution {

  // Using recursive approach
    public static int maxprofit(int[] price, int n){
        
        // Base case
        if (n <= 0) return 0;
            
        // Profit earned
        int ans  = Integer.MIN_VALUE; 
        for (int i = 0; i < n; i++){
            int cut = i + 1;
            int curr_ans = price[i] + maxprofit(price, n - cut);
            ans = Math.max(ans, curr_ans);
        }
        
        return ans;
    } 
    
    public static void main (String[] args){
Scanner s = new Scanner(System.in);
System.out.println("Enter rod length");
int n = s.nextInt();

// Forming price array
int[] price = new int[n];
System.out.println("Enter prices for each length of rod");
for (int i = 0; i < n; i++) price[i] = s.nextInt();

int profit = maxprofit(price,n);

System.out.println("Max Profit Earned "+ profit);
}
}
You can also try this code with Online Java Compiler
Run Code

 

Output:

Enter rod length
8
Enter prices for each length of rod
1 5 8 9 10 17 17 20
Max Profit Earned 22
You can also try this code with Online Java Compiler
Run Code

 

Complexity Analysis

Time Complexity: O(N ^ N), i.e., exponential as we are covering all the prices(or cuts) possible for every price(or cut). Where ‘N’ is the length of the rod (or length of the price array).

Space Complexity: O(1) as no extra space is being used.

Must Read Recursion in Data Structure

Approach 2 - Using Dynamic Programming

We could optimize the time complexity of our previous approach by maintaining a dp array where dp[len] stores the max profit that could be earned from a rod of length ‘len’.

Let's look at the recursive tree:

Dynamic Prograaming Tree

Since the recursive approach had a lot of overlapping subproblems, dp array would also help us avoid that repetitive work.

 

There are 2 approaches to solve this problem via dynamic programming:

 

APPROACH 2a: Via using Unbounded Knapsack

The structure of this problem matches with the knapsack as the price array resembles the value array of the knapsack, the length array (i.e 1 to N) resembles the weight array, and N resembles the max capacity of the knapsack.  

Also, just like there, here too, we had to maximize the profit. At the same time, we have a choice whether to select a piece (i.e. cut at which piece - select or deselect a particular piece value).

Now, this problem is a variation of an unbounded knapsack and not a 0-1 Knapsack, as a particular piece’s length can be taken multiple times. 

Example: For cutting a rod of length 2 (where n = 4): we can either piece it into 2 + 2 or 3+1 

However, in 0-1 Knapsack, an item once taken cannot be chosen again.

 

Implementation

Let’s have a look at its implementation in Java.

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Solution {
 
  // Using 2D dp approach
   public static int maxprofit(int[] price, int[] length, int n, int maxlen, int[][] dp){
        
        // 0 profit earned for 0 length and 0 price
       if (n == 0 || maxlen == 0) return 0;
        
        // Lookup in dp array
       if (dp[n][maxlen] != 0) return dp[n][maxlen];
        
// Depending on profit, choose to take or discard maxlen
if (length[n - 1] <= maxlen) {
dp[n][maxlen] = Math.max(price[n - 1] + maxprofit(price, length, n, maxlen - length[n - 1], dp), 
maxprofit(price, length, n - 1, maxlen, dp));
}

// length > maxlen => discard maxlen
else {
dp[n][maxlen] = maxprofit(price, length, n - 1, maxlen, dp);
}

       return dp[n][maxlen];
    }
public static void main (String[] args){
Scanner s = new Scanner(System.in);
System.out.println("Enter rod length");
int n = s.nextInt();

// Forming price array
int[] price = new int[n];
System.out.println("Enter prices for each length of rod");
for (int i = 0; i < n; i++) price[i] = s.nextInt();

// Creating length array
int length[] = new int[n];
for (int i = 0; i < n; i++) {
length[i] = i + 1;
}

// Creating dp array
int[][] dp = new int[n + 1][n + 1];
int profit = maxprofit(price,length, n, n, dp);

System.out.println("Max Profit Earned for Rod Cutting:"+ profit);
}
}
You can also try this code with Online Java Compiler
Run Code

 

Output:

Enter rod length
8
Enter prices for each length of rod
1 5 8 9 10 17 17 20
Max Profit Earned for Rod Cutting:22
You can also try this code with Online Java Compiler
Run Code

Complexity Analysis

Time Complexity: O(N ^ 2) as for each length we are traversing from 0 to that particular length to calculate our max possible profit for the current length.

Space Complexity: O(N ^ 2) as extra space for storing the max possible profit for each length of rod has been used.

 

Where ‘N’ is the length of the rod (or length of the price array).

 

APPROACH 2b: Optimised Approach

Now, let's try solving the problem in a 1-d dp array, hence optimizing its space complexity.

Earlier, we made a dp array with dimensions [price.length][length] i.e., the size of the price array and rod’s length array to calculate the max profit available for j-th length of the rod.

But now, we could also simply use a given price array and create a 1D dp array to calculate the max profit for i-th length, hence reducing our O(N * N) work to O(N) space complexity.   

 

Implementation

Let’s have a look at its implementation in Java.

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Solution {
 
  // Using 1D dp approach
    public static int maxprofit(int[] price){
        
        int n = price.length;
        int[] dp = new int[n + 1];
        
        // 0 profit earned for 0 length
        dp[0] = 0;
        
        for (int len = 0; len <= n; len++){
            
            // Profit earned
            int ans  = Integer.MIN_VALUE; 
            for (int i = 0; i < len; i++){
                int cut = i + 1;
                int curr_ans = price[i] + dp[len-cut];
                ans = Math.max(ans, curr_ans);
            }
            
            dp[len] = ans;
        } 
        return dp[n];
    }
public static void main (String[] args){
Scanner s = new Scanner(System.in);
System.out.println("Enter rod length");
int n = s.nextInt();

// Forming price array
int[] price = new int[n];
System.out.println("Enter prices for each length of rod");
for (int i = 0; i < n; i++) price[i] = s.nextInt();

int profit = maxprofit(price);

System.out.println("Max Profit Earned for Rod Cutting:"+ profit);
}
}
You can also try this code with Online Java Compiler
Run Code

 

Output:

Enter rod length
8
Enter prices for each length of rod
1 5 8 9 10 17 17 20
Max Profit Earned for Rod Cutting:22
You can also try this code with Online Java Compiler
Run Code

Complexity Analysis

Time Complexity: O(N ^ 2) as for each length we are traversing from 0 to that particular length to calculate our max possible profit for current length.

Space Complexity: O(N) as extra space for storing the max possible profit for each length of rod has been used.

Where ‘N’ is the length of the rod (or length of the price array).

Read More - Time Complexity of Sorting Algorithms

Check out Longest Common Substring

Frequently Asked Questions

What is dynamic programming?

Dynamic programming is both a mathematical and computer programming method mainly used to optimize plain recursion.  

What are two ways to apply dynamic programming?

The two ways to apply dp are bottom-up (i.e., iterative way) and top-down (i.e., using dp in recursion, commonly known as memoization).

What is the best case time complexity for the Rod Cutting Problem?

The best-case time complexity for Rod Cutting Problem is O(1), i.e., when the length of the rod is 0.

Conclusion

In this blog, we learned various approaches to the Rod Cutting Problem.

  • Rod Cutting Problem is a standard recursive problem that is optimized via dynamic Programming.
  • Here we use 1-d dynamic programming where dp[len] stores the max profit that could be earned from a rod of length “len.”
  • The optimized time complexity of this problem is O(N ^ 2) as for each length, we are traversing from 0 to that particular length to calculate our max possible profit for the current length.

 

Check out more blogs on different Dynamic Programming problems like Longest Common Substring and Friends Pairing Problem to read more about these topics in detail.

Refer to our Guided Path on the Coding Ninjas Studio platform regarding Data Structures and Algorithms, Competitive Programming, JavaScript, and many more! where you can find questions asked by all big-tech giants like Amazon, Microsoft, Google, and many more. If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio.

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Live masterclass