Log inSign up
mediumGeeksforGeeksNot Started

Rod Cutting

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on GeeksforGeeks
Lesson

Problem Statement

Given a rod of length n inches and an array of prices price that includes prices of all pieces of size smaller than or equal to n.

Determine the maximum value obtainable by cutting up the rod and selling the pieces.

### Example 1 - Input: price = [1, 5, 8, 9, 10, 17, 17, 20], n = 8 - Output: 22 - Explanation: The maximum obtainable value is 22 by cutting into pieces of lengths 2 and 6 (price 5 + 17 = 22).

### Example 2 - Input: price = [3, 5, 8, 9, 10, 17, 17, 20], n = 8 - Output: 24 - Explanation: The maximum value is 24 by cutting into 8 pieces of length 1 (8 * 3 = 24).

Constraints:

  • 1 <= n <= 1000
  • 1 <= price[i] <= 105

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Model reusable item choices as Unbounded Knapsack.
  • Formulate optimal substructure for 1D rod partitioning.
  • Implement compact 1D dynamic programming.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Cutting a continuous rod into discrete integer pieces.
  • Prices assigned to each piece length; pieces can be reused.

Algorithmic Decision Tree:

  • Outer loop rod length i from 1 to n.
  • Inner loop cut length j from 1 to i.

Connected Patterns:

Coin ChangeUnbounded KnapsackInteger Break

1. Recursive Exhaustive Cutting

Intuition

Recursively try every cut length j from 1 to n and add to optimal price of the remainder.

Algorithm

  1. Define solve(n).
  2. If n <= 0, return 0.
  3. Initialize maxVal = -inf.
  4. For j = 1 to n:
  5. maxVal = max(maxVal, price[j - 1] + solve(n - j)).
  6. Return maxVal.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 int solve(int n, const vector<int>& price) {
9 if (n <= 0) return 0;
10 int maxVal = 0;
11 for (int j = 1; j <= n; ++j) {
12 maxVal = max(maxVal, price[j - 1] + solve(n - j, price));
13 }
14 return maxVal;
15 }
16public:
17 int cutRod(vector<int>& price, int n) {
18 return solve(n, price);
19 }
20};
21
22int main() {
23 Solution sol;
24 vector<int> price = {1, 5, 8, 9, 10, 17, 17, 20};
25 cout << "Max Value: " << sol.cutRod(price, 8) << endl;
26 return 0;
27}

Time & Space Complexity

  • Time complexity: O(2^n)
  • Space complexity: O(n) call stack

2. Memoized Top-Down DP

Intuition

Store intermediate results for each remaining length in a memo array of size n + 1.

Algorithm

  1. Initialize memo array of size n + 1 with -1.
  2. In solve(rem): return memo[rem] if already computed.
  3. Try all cut sizes j from 1 to rem.
  4. Store and return memo[rem].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 int solve(int rem, const vector<int>& price, vector<int>& memo) {
9 if (rem <= 0) return 0;
10 if (memo[rem] != -1) return memo[rem];
11
12 int maxVal = 0;
13 for (int j = 1; j <= rem; ++j) {
14 maxVal = max(maxVal, price[j - 1] + solve(rem - j, price, memo));
15 }
16
17 return memo[rem] = maxVal;
18 }
19public:
20 int cutRod(vector<int>& price, int n) {
21 vector<int> memo(n + 1, -1);
22 return solve(n, price, memo);
23 }
24};
25
26int main() {
27 Solution sol;
28 vector<int> price = {1, 5, 8, 9, 10, 17, 17, 20};
29 cout << "Max Value: " << sol.cutRod(price, 8) << endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(n^2)
  • Space complexity: O(n)

3. 1D Bottom-Up Tabulation (O(n^2) Time, O(n) Space)

Intuition

Tabulate dp[i] where dp[i] is the maximum profit for a rod of length i, using a compact 1D array.

Algorithm

  1. Initialize dp array of size n + 1 with 0.
  2. Loop rod length i from 1 to n:
  3. Loop cut length j from 1 to i:
  4. dp[i] = max(dp[i], price[j - 1] + dp[i - j]).
  5. Return dp[n].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int cutRod(vector<int>& price, int n) {
10 vector<int> dp(n + 1, 0);
11
12 for (int i = 1; i <= n; ++i) {
13 for (int j = 1; j <= i; ++j) {
14 dp[i] = max(dp[i], price[j - 1] + dp[i - j]);
15 }
16 }
17
18 return dp[n];
19 }
20};
21
22int main() {
23 Solution sol;
24 vector<int> price = {1, 5, 8, 9, 10, 17, 17, 20};
25 cout << "Max Value: " << sol.cutRod(price, 8) << endl;
26 return 0;
27}

Time & Space Complexity

  • Time complexity: O(n^2)
  • Space complexity: O(n)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive CuttingO(2^n)O(n)Exhaustive branching over all cut lengths.Repeated rod length subproblems
2.Memoized DPO(n^2)O(n)Store max value for each rod length in memo array.None
3.1D Bottom-Up TabulationOptimalO(n^2)O(n)Iteratively fill dp array from length 1 to n.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

1-based vs 0-based indexing: price[j - 1] corresponds to a cut of length j.

Pitfall 2:

Limiting each cut length to be used at most once.

Crucial Edge Cases to Validate:

  • n = 1: Only 1 cut option; returns price[0].
  • Price of full length rod is already optimal: e.g. price[n-1] is very high; returns price[n-1].

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention that this problem is structurally identical to the Unbounded Knapsack problem and Integer Break.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is Rod Cutting an Unbounded Knapsack problem rather than a 0/1 Knapsack problem?

Back to DSA Sheet