Rod Cutting

Problem Link

Rod Cutting - GFG

Problem Statement

You are given a rod of length n and a price array of size n where price[i] denotes the price of a rod of length i+1. You can cut the rod in various sizes and sell the pieces. Find the maximum total value you can obtain by cutting up the rod and selling the pieces.

Examples

Input

n = 8  
price[] = {1, 5, 8, 9, 10, 17, 17, 20}

Output

22

Choice Diagram

At each index i, we have two choices:

          +------------------+
          |  Rod Length = i  |
          +------------------+
            /           \
         Pick         Not Pick
     Add price[i]     Move to i-1
     Reduce length     Same length

Step 1: Recursion (TLE)

IBH

• Induction: What is the result of f(i, length)?

• Base: If i == 0, only cut in 1-length pieces.

• Hypothesis: f(i-1, length) gives max value without picking i.

• Induction: Try both pick and not pick, and take the max.

public class Solution {
    public static int cutRod(int[] price, int n) {
        return f(price.length - 1, n, price);
    }

    static int f(int i, int length, int[] price) {
        if (i == 0) {
            return length * price[0]; // all 1-length cuts
        }

        int notPick = f(i - 1, length, price);
        int pick = Integer.MIN_VALUE;
        int rodLength = i + 1;
        if (rodLength <= length) {
            pick = price[i] + f(i, length - rodLength, price); // pick same index (unbounded)
        }

        return Math.max(pick, notPick);
    }
}

• Time Complexity: Exponential O(2^n)

• Space Complexity: O(n) (stack space)

Step 2: Memoization

import java.util.*;

public class Solution {
    public static int cutRod(int[] price, int n) {
        int[][] dp = new int[n][n + 1];
        for (int[] row : dp) Arrays.fill(row, -1);
        return f(n - 1, n, price, dp);
    }

    static int f(int i, int length, int[] price, int[][] dp) {
        if (i == 0) {
            return length * price[0];
        }

        if (dp[i][length] != -1) return dp[i][length];

        int notPick = f(i - 1, length, price, dp);
        int pick = Integer.MIN_VALUE;
        int rodLength = i + 1;
        if (rodLength <= length) {
            pick = price[i] + f(i, length - rodLength, price, dp);
        }

        return dp[i][length] = Math.max(pick, notPick);
    }
}

• Time Complexity: O(n²)

• Space Complexity: O(n²) + O(n) recursion

Step 3: Tabulation (Bottom-Up DP)

import java.util.*;

public class Solution {
    public static int cutRod(int[] price, int n) {
        int[][] dp = new int[n][n + 1];

        // Base case: only using 1-length rods
        for (int length = 0; length <= n; length++) {
            dp[0][length] = length * price[0];
        }

        for (int i = 1; i < n; i++) {
            for (int length = 0; length <= n; length++) {
                int notPick = dp[i - 1][length];
                int pick = Integer.MIN_VALUE;
                int rodLength = i + 1;

                if (rodLength <= length) {
                    pick = price[i] + dp[i][length - rodLength];
                }

                dp[i][length] = Math.max(pick, notPick);
            }
        }

        return dp[n - 1][n];
    }
}

• Time Complexity: O(n²)

• Space Complexity: O(n²)

Step 4: Space Optimization

We just need the previous row and current row, so optimize using two 1D arrays:

import java.util.*;

public class Solution {
    public static int cutRod(int[] price, int n) {
        int[] prev = new int[n + 1];

        // Base case
        for (int length = 0; length <= n; length++) {
            prev[length] = length * price[0];
        }

        for (int i = 1; i < n; i++) {
            int[] curr = new int[n + 1];
            for (int length = 0; length <= n; length++) {
                int notPick = prev[length];
                int pick = Integer.MIN_VALUE;
                int rodLength = i + 1;

                if (rodLength <= length) {
                    pick = price[i] + curr[length - rodLength]; // use curr to allow unlimited cuts
                }

                curr[length] = Math.max(pick, notPick);
            }
            prev = curr;
        }

        return prev[n];
    }
}

• Time Complexity: O(n²)

• Space Complexity: O(n)

Conclusion