Rod Cutting Editorial

Practice Problem Link: Rod Cutting | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

You are given a rod of length n, and an array prices of size n which contains the prices of rods of lengths 1 to n. Find the maximum amount you can make if you cut up the rod optimally.

Naive Approach

The naive approach is to generate all the possible configurations of cutting the rod, and then find the maximum amount which can be generated from all these configurations. This can be achieved by a brute force recursion.

Analysis

• Time Complexity: Exponential
• Space Complexity: O(1)

Implementation

C++

int maximumProfitUtil(int n, vector<int> &prices) {
   if (n == 0) {
       return 0;
   }
   int maxProfit = INT_MIN;
   for (int i = 1; i <= n; i++) {
       maxProfit = max(maxProfit, prices[i - 1] + maximumProfitUtil(n - i, prices));
   }
   return maxProfit;
}
int maximumProfit(int n, vector<int> prices) {
   return maximumProfitUtil(n, prices);
}

Java

class Solution {
   int maximumProfitUtil(int n, int[] prices) {
       if (n == 0) {
           return 0;
       }
       int maxProfit = Integer.MIN_VALUE;
       for (int i = 1; i <= n; i++) {
           maxProfit = Math.max(maxProfit, prices[i - 1] + maximumProfitUtil(n - i, prices));
       }
       return maxProfit;
   }
   
   int maximumProfit(int n, int[] prices) {
       return maximumProfitUtil(n, prices);
   }
}

Optimal Approach

Observe that in the naive approach multiple function calls are getting repeated and recalculated redundantly. We can memoize those recursive calls using Dynamic Programming and reduce our time complexity to polynomial order.

Analysis

• Time Complexity: O(n²)
• Space Complexity: O(n)

Implementation (Recursive)

C++

vector<int> dp;
int maximumProfitUtil(int n, vector<int> &prices) {
   if (n == 0) {
       return 0;
   }
   if (dp[n] != -1) {
       return dp[n];
   }
   int maxProfit = INT_MIN;
   for (int i = 1; i <= n; i++) {
       maxProfit = max(maxProfit, prices[i - 1] + maximumProfitUtil(n - i, prices));
   }
   dp[n] = maxProfit;
   return maxProfit;
}
int maximumProfit(int n, vector<int> &prices) {
   dp.assign(n + 1, -1);
   return maximumProfitUtil(n, prices);
}

Java

class Solution {
   int[] dp = new int[0];
   int maximumProfitUtil(int n, int[] prices) {
       if (n == 0) {
           return 0;
       }
       if (dp[n] != -1) {
           return dp[n];
       }
       int maxProfit = Integer.MIN_VALUE;
       for (int i = 1; i <= n; i++) {
           maxProfit = Math.max(maxProfit, prices[i - 1] + maximumProfitUtil(n - i, prices));
       }
       dp[n] = maxProfit;
       return maxProfit;
   }
   
   int maximumProfit(int n, int[] prices) {
       dp = new int[n + 1];
       Arrays.fill(dp, -1);
       return maximumProfitUtil(n, prices);
   }
}

Implementation (Iterative)

C++

vector<int> dp;
int rodCut(vector<int> &prices, int n) {
   dp[0] = 0;
   if(n <= 0) {
       return 0;
   }
   int max_value = INT_MIN;
   for(int i = 1; i <= n; i++) {
       for(int j = 0; j < i; j++) {
           max_value = max(max_value, prices[j] + dp[i - j - 1]);
       }
       dp[i] = max_value;
   }
   return dp[n];
}
int maximumProfit(int n, vector<int> prices) {
   dp.assign(n + 1, 0);
   return rodCut(prices, n);
}

Java

class Solution {
   int dp[];
   int rodCut(int[] prices, int n) {
       dp[0] = 0;
       if(n <= 0) {
           return 0;
       }
       int maxValue = Integer.MIN_VALUE;
       for(int i = 1; i <= n; i++) {
           for(int j = 0; j < i; j++) {
               maxValue = Math.max(maxValue, prices[j] + dp[i - j - 1]);
           }
           dp[i] = maxValue;
       }
       return dp[n];
   }
   int maximumProfit(int n, int[] prices) {
       dp = new int[n + 1];
       return rodCut(prices, n);
   }
}