Rod Cutting

Problem

Given a rod of length n inches and an array price[], where price[i] denotes the value of a piece of length i. Your task is to determine the maximum value obtainable by cutting up the rod and selling the pieces. (link)

Note: n = size of price, and price[] is 1-indexed array.

Example:

Input: price[] = [1, 5, 8, 9, 10, 17, 17, 20]
Output: 22
Explanation: The maximum obtainable value is 22 by cutting in two pieces of lengths 2 and 6, i.e., 5 + 17 = 22.

Input: price[] = [3, 5, 8, 9, 10, 17, 17, 20]
Output: 24
Explanation: The maximum obtainable value is 24 by cutting the rod into 8 pieces of length 1, i.e, 8*price[1] = 8*3 = 24.

Input: price[] = [3]
Output: 3
Explanation: There is only 1 way to pick a piece of length 1.

Solution

We need to cut the rod into pieces. If a piece is i centimeters long, we can sell it at the price for i. We can cut the rod into pieces of the same length. For example, if the rod is 5 cm long, we can cut it into multiple 5 cm pieces and sell each at the rate for 5 cm. There is no restriction on cutting the remaining piece into 5 cm sections.

The main idea follows a "take or not take" pattern. First, we consider taking a piece, and then we explore the problem by considering the opposite approach. Instead of cutting the rod into pieces, we think about taking pieces and ensuring their total length matches the rod's length. For instance, we might take an ith piece and then consider the combinations or possibilities of the next pieces of the same length. The "not take" condition means we don't consider that particular ith piece.

Recursion

Time - O(2^n)

Space - O(n) - stack space

class Solution {
    
    private int cutRod(int index, int length, int price[]){
        if(index==0){
          return length * price[0];
        }
        
        int take = 0;
        
        int rodLength = index + 1;
        
        if(length-rodLength>=0){
            take = price[index] + cutRod(index, length-rodLength, price);
        }
        
        int notTake = cutRod(index-1, length, price);
        
        return Math.max(take, notTake);
    }
    
    public int cutRod(int[] price) {
        int n = price.length;
        return cutRod(n-1, n, price);
    }
}

Memoization

Time - O(nxn)

Space - O(nxn) + O(n)

class Solution {
    
    private int cutRod(int index, int length, int price[], int[][] dp){
        
        if(index==0){
          return length * price[0];
        }
        
        if(dp[index][length] != -1) return dp[index][length];
        
        int take = 0;
        
        int rodLength = index + 1;
        
        if(length-rodLength>=0){
            take = price[index] + cutRod(index, length-rodLength, price, dp);
        }
        
        int notTake = cutRod(index-1, length, price,dp);
        
        return dp[index][length] = Math.max(take, notTake);
    }
    
    public int cutRod(int[] price) {
        int n = price.length;
        int[][] dp = new int[n][n+1];
        for(int[] row : dp) {
            Arrays.fill(row, -1);
        }
        return cutRod(n-1, n, price, dp);
    }
}

Tabulation

Time - O(nxn)

Space - O(nxn)

class Solution {
    
    public int cutRod(int[] price) {
        int n = price.length;
        int[][] dp = new int[n][n+1];
        
        for(int length=1; length<=n; length++){
            dp[0][length] = price[0] * length;
        }
        
        for(int index=1; index<n; index++){
            for(int length=0; length<=n; length++){
                int take = 0;
                int rodLength = index + 1;
                if(length-rodLength>=0){
                    take = price[index] + dp[index][length-rodLength];
                }
                
                int notTake = dp[index-1][length];
                
                dp[index][length] = Math.max(take, notTake);
            }
        }
        
        return dp[n-1][n];
    }
}

Space Optimization

Time - O(nxn)

Space - O(n)

class Solution {
    public int cutRod(int[] price) {
        int n = price.length;
        
        int[] prev = new int[n+1];
        
        for(int length=1; length<=n; length++){
            prev[length] = price[0] * length;
        }
        
        for(int index=1; index<n; index++){
            int[] curr = new int[n+1];
            for(int length=0; length<=n; length++){
                int take = 0;
                int rodLength = index + 1;
                if(length-rodLength>=0){
                    take = price[index] + curr[length-rodLength];
                }
                
                int notTake = prev[length];
                
                curr[length] = Math.max(take, notTake);
            }
            prev = curr;
        }
        return prev[n];
    }
}