Rod Cutting

Medium
1601.

Rod Cutting

Rod Cutting is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google and Microsoft interviews.

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 <= 1000
  • 1 <= price[i] <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} price
 * @return {number}
 */
var cutRod = function(price) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 1000
  • 1 <= price[i] <= 10^5

Hints for Rod Cutting

  1. 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.

  2. Hint 2

    Let best[len] be the most a rod of length len can earn. Then best[len] = max over i of price[i - 1] + best[len - i].

  3. Hint 3

    Fill best for len = 1, 2, …, n in 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

  1. Set best[0] = 0.
  2. For len from 1 to n: best[len] = max(price[i - 1] + best[len - i]) over i = 1 … len.
  3. 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 length i — the array is 0-indexed, lengths are 1-indexed.
  • Selling the rod uncut is the case i = len, with best[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