Rod Cutting Problem: Maximize Revenue with DP

105.2k
0

An integer array price contains the selling price of every possible rod-piece length. Each zero-based array position maps to a piece length one unit larger than the position. The complete rod has length n.

Cut the rod into integer-length pieces with a total length equal to n. Any piece length may be used any number of times. Return the maximum total selling price. Selling the complete rod without a cut remains a valid choice.

Example 1

Input: price = [2, 5, 7, 8, 10], n = 5
Output: 12
Explanation: Piece lengths 2 and 3 use the complete rod and earn 5 + 7 = 12, the largest possible revenue.

Example 2

Input: price = [3], n = 1
Output: 3
Explanation: Only one piece of length 1 is available, so selling the complete rod earns 3.

Recursion

Every piece length creates two choices: skip the current length or take it. Skipping moves to shorter piece lengths, while taking a piece earns its price and reduces the remaining rod length. Since a piece length can be used multiple times, the take choice keeps the same index available.

The state solve(index, rodLength) represents the maximum revenue obtainable using piece lengths 1 through index + 1 for a rod of length rodLength. The initial call uses n - 1 and n because all piece lengths and the complete rod are available.

Algorithm

  • Define solve(index, rodLength) as the maximum revenue using piece lengths 1 through index + 1, so each state captures the available lengths and remaining rod.

  • Handle index == 0 by filling the remaining rod with length-1 pieces, because this is the only available piece length.

  • Explore solve(index - 1, rodLength) to skip the current piece length, leaving the rod unchanged for shorter lengths.

  • Initialize the take revenue with a very small sentinel so an oversized piece cannot become the best choice.

  • Explore solve(index, rodLength - (index + 1)) when the current piece fits, keeping the same index because the piece length can be used again.

  • Add price[index] to the take result because one piece of the current length contributes its price to the revenue.

  • Return the larger of the take and skip results because the better valid choice gives the maximum revenue for the current state.

Dry Run

Diagram 1
1 / 3

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Finds the best revenue for one recursive state.
int solve(
int index,
int rodLength,
vector<int>& price
) {
// Length one always fills the remaining rod.
if (index == 0) {
return rodLength * price[0];
}
// Skipping exposes only shorter piece lengths.
int notTake = solve(
index - 1,
rodLength,
price
);
// The sentinel rejects an unavailable take choice.
int take = -1000000000;
int pieceLength = index + 1;
// A fitting piece leaves a valid smaller rod.
if (pieceLength <= rodLength) {
// The same index permits another equal piece.
int remainingRevenue = solve(
index,
rodLength - pieceLength,
price
);
// The chosen piece adds price to the remainder.
take = price[index] + remainingRevenue;
}
// The better valid choice maximizes the revenue.
return max(notTake, take);
}
public:
// Returns the maximum revenue for the complete rod.
int cutRod(vector<int>& price, int n) {
// The last index exposes every piece length.
return solve(n - 1, n, price);
}
};
// Driver code
int main() {
vector<int> price = {2, 5, 7, 8, 10};
int n = 5;
Solution obj;
cout << obj.cutRod(price, n);
return 0;
}

Complexity Analysis

Time Complexity: O(4N), where N is the rod length, because each state can branch into take and skip choices, and a root-to-leaf path contains at most N skips plus N length reductions.

Space Complexity: O(N), because the deepest recursive path contains at most a linear number of skipped lengths and taken pieces.

Note: Direct recursion may fail for large input values. Repeated subproblems create exponential work, so an online judge may report Time Limit Exceeded.

Memoization

Direct recursion reaches the same (index, rodLength) state through several cut sequences. Recomputing an identical state repeats an entire decision subtree even though the best revenue cannot change.

A two-dimensional dp array stores one answer for every state. A cached entry returns immediately, while an unseen state follows the unchanged recursive choices and saves the final maximum before returning.

Algorithm

  • Create a dp table with n rows and n + 1 columns, filled with -1, so every untouched entry marks an uncalculated state.

  • Define the same solve(index, rodLength) state used by direct recursion, preserving the piece choices and base case without alteration.

  • Handle index = 0 with length-1 pieces because the smallest available length completes every remaining rod exactly.

  • Return dp[index][rodLength] whenever a stored value exists, preventing another traversal of an already solved decision subtree.

  • Compute the skip branch from index - 1, preserving the remaining rod while removing the current piece length.

  • Compute a valid take branch from the same index, allowing another equal piece after reducing the remaining rod.

  • Store and return the larger branch revenue because the cached maximum completely represents the current state.

Dry Run

Diagram 1
1 / 3

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Finds and caches one state revenue.
int solve(
int index,
int rodLength,
vector<int>& price,
vector<vector<int>>& dp
) {
// Length one always fills the remaining rod.
if (index == 0) {
return rodLength * price[0];
}
// A stored answer avoids repeated recursion.
if (dp[index][rodLength] != -1) {
return dp[index][rodLength];
}
// Skipping exposes only shorter piece lengths.
int notTake = solve(
index - 1,
rodLength,
price,
dp
);
// The sentinel rejects an unavailable take choice.
int take = -1000000000;
int pieceLength = index + 1;
// A fitting piece leaves a valid smaller rod.
if (pieceLength <= rodLength) {
// The same index permits another equal piece.
int remainingRevenue = solve(
index,
rodLength - pieceLength,
price,
dp
);
// The chosen piece adds price to the remainder.
take = price[index] + remainingRevenue;
}
// The maximum is cached for later state visits.
dp[index][rodLength] = max(notTake, take);
return dp[index][rodLength];
}
public:
// Returns the maximum revenue for the complete rod.
int cutRod(vector<int>& price, int n) {
// Every item-length state starts uncalculated.
vector<vector<int>> dp(
n,
vector<int>(n + 1, -1)
);
// The last index exposes every piece length.
return solve(n - 1, n, price, dp);
}
};
// Driver code
int main() {
vector<int> price = {2, 5, 7, 8, 10};
int n = 5;
Solution obj;
cout << obj.cutRod(price, n);
return 0;
}

Complexity Analysis

Time Complexity: O(N2), where N is the rod length, because at most N × (N + 1) reachable states are calculated once after the cache lookup.

Space Complexity: O(N2), because the dp table stores N × (N + 1) values, while the recursion stack adds only O(N) additional space.

Tabulation

Memoization already reveals every dependency. A state needs the previous row at the same rod length for skipping and the current row at a smaller rod length for taking. Bottom-up evaluation can prepare both values before the current state.

The base row uses only length-1 pieces. Later rows are filled from shorter piece lengths toward longer piece lengths, while rod lengths move upward so repeated use of the current piece reads an already completed current-row state.

Algorithm

  • Create an n by n + 1 table named dp, because every price index and remaining rod length forms one possible state.

  • Fill the base row as rodLength * price[0], because length-1 pieces are the only available choice at index 0.

  • Process price indices from 1 through n - 1, ensuring the previous row already contains every skip answer.

  • Scan current rod lengths from 0 through n, so a smaller current-row state is ready before a repeated take needs the state.

  • Read dp[index - 1][rodLength] as the skip revenue because skipping removes the current piece length.

  • Read price[index] + dp[index][rodLength - pieceLength] for a fitting take because the current row keeps the same piece length reusable.

  • Store the larger revenue in dp[index][rodLength] because each cell must preserve the best valid choice, then return dp[n - 1][n] as the full problem answer.

Dry Run

Rod Cutting Problem Tabulation

Rod Cutting Problem Tabulation

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the maximum revenue for the complete rod.
int cutRod(vector<int>& price, int n) {
// One cell represents an item-length state.
vector<vector<int>> dp(
n,
vector<int>(n + 1, 0)
);
// The base row uses only length-one pieces.
for (int rodLength = 0;
rodLength <= n;
rodLength++) {
dp[0][rodLength] = rodLength * price[0];
}
// Each pass introduces one longer piece.
for (int index = 1; index < n; index++) {
int pieceLength = index + 1;
// Ascending lengths allow repeated pieces.
for (int rodLength = 0;
rodLength <= n;
rodLength++) {
// The previous row supplies the skip value.
int notTake = dp[index - 1][rodLength];
// The sentinel rejects an unavailable take.
int take = -1000000000;
// A fitting piece reads the current row.
if (pieceLength <= rodLength) {
// Current-row reuse allows equal pieces.
int remainingRevenue =
dp[index][rodLength - pieceLength];
// One piece adds price to the remainder.
take = price[index] + remainingRevenue;
}
// The larger choice completes the state.
dp[index][rodLength] =
max(notTake, take);
}
}
// The final cell represents every allowed choice.
return dp[n - 1][n];
}
};
// Driver code
int main() {
vector<int> price = {2, 5, 7, 8, 10};
int n = 5;
Solution obj;
cout << obj.cutRod(price, n);
return 0;
}

Complexity Analysis

Time Complexity: O(N2), where N is the rod length, because the nested loops fill N × (N + 1) states with constant work per state.

Space Complexity: O(N2), because the iterative dp table stores one revenue value for every price-index and rod-length pair, without requiring recursion stack space.

Space Optimization

The tabulation transition needs a previous-row skip value and a current-row take value at a smaller rod length. A single dp array can hold both values during an ascending rod-length scan.

Before each update, dp[rodLength] still stores the previous-row skip revenue. A smaller array position already stores the current-row take remainder. Calculating current before replacing dp[rodLength] preserves both choices in the required order.

Algorithm

  • Create a one-dimensional dp array of size n + 1, because only one revenue per rod length remains necessary during a logical row update.

  • Fill dp[rodLength] as rodLength * price[0], preserving the tabulation base row made from length-1 pieces.

  • Process price indices from 1 through n - 1, so each pass introduces one longer piece length.

  • Scan rod lengths in increasing order, allowing dp[rodLength - pieceLength] to contain the updated current-row take remainder.

  • Read dp[rodLength] before replacement as the skip value, because the old entry still represents the previous logical row.

  • Calculate current as the larger skip or valid take revenue, preserving both choices before any array replacement.

  • Store current into dp[rodLength] so the logical row advances safely, then return dp[n] as the complete-rod optimum.

Dry Run

Rod Cutting Problem Space Optimization

Rod Cutting Problem Space Optimization

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the maximum revenue for the complete rod.
int cutRod(vector<int>& price, int n) {
// One entry stores the best revenue per length.
vector<int> dp(n + 1, 0);
// The initial row uses length-one pieces.
for (int rodLength = 0;
rodLength <= n;
rodLength++) {
dp[rodLength] = rodLength * price[0];
}
// Each pass replaces one logical table row.
for (int index = 1; index < n; index++) {
int pieceLength = index + 1;
// Ascending lengths allow repeated pieces.
for (int rodLength = 0;
rodLength <= n;
rodLength++) {
// The old entry supplies the skip value.
int notTake = dp[rodLength];
// The sentinel rejects an unavailable take.
int take = -1000000000;
// A fitting piece reads an updated entry.
if (pieceLength <= rodLength) {
// A smaller entry permits equal pieces.
int remainingRevenue =
dp[rodLength - pieceLength];
// One piece adds price to the remainder.
take = price[index] + remainingRevenue;
}
// Current preserves both choices first.
int current = max(notTake, take);
// The shift advances the logical row safely.
dp[rodLength] = current;
}
}
// The final entry represents the complete rod.
return dp[n];
}
};
// Driver code
int main() {
vector<int> price = {2, 5, 7, 8, 10};
int n = 5;
Solution obj;
cout << obj.cutRod(price, n);
return 0;
}

Complexity Analysis

Time Complexity: O(N2), where N is the rod length, because the nested item and rod-length loops perform constant work for every state.

Space Complexity: O(N), because the one-dimensional dp array stores one maximum revenue value per rod length.

Interview follow-up Questions

Yes. Every piece length has unlimited availability, so a take transition keeps the same price index for another possible selection.

Dynamic Programming

Read Similar Blogs

Dynamic Programming

Largest Divisible Subset

Given an array nums containing distinct positive integers, return a maximum-length subset. For every pair of values first and second in the subset, either first % second == 0 or second % first == 0...

73.5k
Dynamic Programming

Best Time to Buy and Sell Stock IV: At Most K Transactions

Given an integer k and an array prices , prices[day] stores the stock price on a particular day. At most k transactions may be completed. One transaction contains one buy followed by one sell. A se...

50.8k
Dynamic Programming

Best Time to Buy and Sell Stock with Transaction Fee

An array prices stores a stock price for each day, and an integer fee gives the cost of one completed transaction. Any number of transactions may be completed, but only one share may be held at a t...

65.7k
Comments0