Rod Cutting — Solution in Python, Java & C++
Rod Cutting solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.
Rod Cutting is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You have a rod of length n, where n is the length of the array price. A piece of length i (for 1 <= i <= n) sells for price[i - 1].
You may cut the rod into any number of pieces of whole-number lengths (or not cut it at all) and sell every piece. Pieces of the same length may be sold as many times as you produce them.
Return the maximum total amount you can earn.
Example 1
Input: price = [1,5,8,9,10,17,17,20]
Output: 22
Explanation: Cut the rod of length 8 into pieces of length 2 and 6: 5 + 17 = 22.
Example 2
Input: price = [3,5,8,9,10,17,17,20]
Output: 24
Explanation: Eight pieces of length 1 earn 8 * 3 = 24.
Example 3
Input: price = [7]
Output: 7
Explanation: A rod of length 1 can only be sold whole.
Constraints
1 <= n == price.length <= 10001 <= price[i] <= 10^5
Hints for Rod Cutting
Hint 1
Think about the length of the first piece you cut off. Whatever is left is a smaller rod with the same price list.
Hint 2
Let
best[len]be the most a rod of lengthlencan earn. Thenbest[len] = max over i of price[i - 1] + best[len - i].Hint 3
Fill
bestforlen = 1, 2, …, nin order;best[0] = 0. This is the unbounded knapsack with lengths as weights.
How to solve Rod Cutting
Every way of cutting a rod starts with some first piece of length i; the rest is an independent rod of length len - i that should itself be cut optimally. That gives a one-dimensional recurrence over the rod length.
Approach
- Set
best[0] = 0. - For
lenfrom 1 ton:best[len] = max(price[i - 1] + best[len - i])overi = 1 … len. - Return
best[n].
Why it works
Fix an optimal cutting of length len and let its first piece have length i. The remaining pieces form a cutting of length len - i; if a better cutting of that remainder existed, swapping it in would beat the optimum. So the optimum equals price[i - 1] + best[len - i] for some i, and taking the maximum over all i finds it.
Complexity
- Time —
O(n^2) - Space —
O(n)
Pitfalls
price[i - 1]is the price of lengthi— the array is 0-indexed, lengths are 1-indexed.- Selling the rod uncut is the case
i = len, withbest[0] = 0. - The answer is at most
n * max(price) = 10^8, so 32-bit integers suffice.
Reference solution
Python
from typing import List
def cutRod(price: List[int]) -> int:
n = len(price)
best = [0] * (n + 1)
for length in range(1, n + 1):
top = 0
for i in range(1, length + 1):
cand = price[i - 1] + best[length - i]
if cand > top:
top = cand
best[length] = top
return best[n]Java
public static int cutRod(int[] price) {
int n = price.length;
int[] best = new int[n + 1];
for (int len = 1; len <= n; len++) {
int top = 0;
for (int i = 1; i <= len; i++) top = Math.max(top, price[i - 1] + best[len - i]);
best[len] = top;
}
return best[n];
}C++
int cutRod(vector<int>& price) {
int n = price.size();
vector<int> best(n + 1, 0);
for (int len = 1; len <= n; len++) {
int top = 0;
for (int i = 1; i <= len; i++) top = max(top, price[i - 1] + best[len - i]);
best[len] = top;
}
return best[n];
}JavaScript
var cutRod = function(price) {
var n = price.length;
var best = new Array(n + 1).fill(0);
for (var len = 1; len <= n; len++) {
var top = 0;
for (var i = 1; i <= len; i++) {
if (price[i - 1] + best[len - i] > top) top = price[i - 1] + best[len - i];
}
best[len] = top;
}
return best[n];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming