Cutting a Rod

Problem Statement

The problem “Cutting a Rod” states that you are given a rod of some particular length and prices for all sizes of rods which are smaller than or equal to the input length. That is we know the price for rods of length from 1 to n, considering the length of the rod was n. One thing to notice here is that the price for the rod of different lengths is not equally distributed. Some rods with a certain length have higher prices than others. These rods may or may have more length as compared to other rods of different lengths.

Example

length = 1 2 3 4 5 6 7
price = 4 5 6 7 7 1 1

28

Explanation: The best we can do is take 7 rods of length which can give us the best result of cost 28.

Approach

So for solving this problem, one can think of solving the problem recursively. And the approach is fairly correct. So let’s discuss how can we solve the problem using recursion. We can try to cut the rod in segments of different lengths. Then we calculate the price for the rods which are formed after cutting all the rods. But when we are saying that we need to find all the ways of cutting the rods. This operation is very costly and has exponential time complexity. So we need to somehow reduce these computations. An optimization could be if we add the cost of a segment of the rod at the time of cutting. Then solve the problem again with a smaller rod. But this is not good enough, this algorithm still takes exponential time.

The recursive formula for the cutting a rod problem is

cuttingRod(n) = max(cost[i] + cuttingRod(n-i-1)) where i is in range from 0 to n-1

So, if we take a brief moment to see how the algorithm is working. We can see that we are calling cuttingRod(n-1), cuttingRod(n-2), …, cuttingRod(1) which then again keeps on calling cuttingRod. Since cuttingRod(i) is called multiple times. It’s better if we store these values. So we are going to use Dynamic Programming to reduce these unnecessary computations.

Code

C++ code for cutting rod

#include<bits/stdc++.h>
using namespace std;

int cuttingRod(vector<int> &cost) 
{
  int n = cost.size();
  int dp[n+1]; dp[0] = 0;

  for(int i=1;i<=n;i++){
    dp[i] = INT_MIN;
    for(int j=0;j<i;j++)
      dp[i] = max(dp[i], cost[j]+dp[i-j-1]);
  }
  return dp[n];
} 

int main(){
  // length of input rod
  int n;cin>>n;
  // store prices for length 1 to n
  vector<int> cost(n);
  for(int i=0;i<n;i++)
    cin>>cost[i];
  int maxCost = cuttingRod(cost);
  cout<<maxCost;
}

7
4 5 6 7 7 1 1

28

Java code for cutting rod

import java.util.*;
class Main{
  
  static int cuttingRod(ArrayList<Integer> cost){
    int n = cost.size();
    int dp[] = new int[n+1];
    dp[0] = 0;

    for(int i=1;i<=n;i++){
      dp[i] = Integer.MIN_VALUE;
      for(int j=0;j<i;j++)
        dp[i] = Math.max(dp[i], cost.get(j)+dp[i-j-1]);
    }
    return dp[n];
  }
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    // length of input rod
    int n = sc.nextInt();
    // store prices for length 1 to n
    ArrayList<Integer> cost = new ArrayList<Integer>();
    for(int i=0;i<n;i++){
      int a = sc.nextInt();
      cost.add(a);
    }
    int maxCost = cuttingRod(cost);
    System.out.println(maxCost);
  }
}

7
4 5 6 7 7 1 1

28

Complexity Analysis

Time Complexity

O(N^2), because we are using a bottom-up DP approach and keep on updating the cost of smaller length rods. This allows reducing the problem which was solved in exponential time to polynomial time.

Space Complexity

O(N), because the space is being used for storing the values in DP table.