Rod Cutting Problem

Problem

You are given a rod of integer length n (n >= 0) and an array price where price[i-1] gives the selling price of a piece of length i (1-indexed logic). You may cut the rod into any number of integer-length pieces (or not cut at all). Find the maximum obtainable revenue by cutting and selling the pieces. (Assume unlimited demand; each piece sells for the listed unit price.)

Return the maximum revenue; optionally reconstruct one optimal set of cuts.

This is a classic introductory Dynamic Programming problem (unbounded variant of the knapsack formulation) often appearing right after Fibonacci when teaching overlapping subproblems and optimal substructure.

Details

• All lengths are positive integers.
• A piece of length i can be used multiple times (unbounded usage).
• If n = 0, revenue is 0.

Examples

Example 1

Input: n = 4, price = [1, 5, 8, 9]
Output: 10
Explanation: Best is 2 + 2 (price[2] + price[2] = 5 + 5). Single piece length 4 yields 9.

Example 2

Input: n = 5, price = [2, 3, 7, 8, 9]
Output: 11
Explanation: Optimal decomposition: 2 + 3 (price[2] + price[3] = 3 + 7 = 10) is not best; better is 1 + 1 + 3 (2 + 2 + 7 = 11) or 2 + 2 + 1 (3 + 3 + 2 = 8 < 11). Answer = 11.

Example 3

Input: n = 8, price = [1,5,8,9,10,17,17,20]
Output: 22
Explanation: One optimal: 2 + 6 (5 + 17 = 22). Plain 8 gives 20.

Example 4 (Edge)

Input: n = 0, price = []
Output: 0
Explanation: Empty rod yields zero revenue.

Solution

Core idea: For each length L, consider the first cut at position i (1 ≤ i ≤ L) and combine the price of the left piece with the optimal revenue of the remaining length: best[L] = max_{1 ≤ i ≤ L} ( price[i] + best[L - i] ). This naturally forms overlapping subproblems. Multiple DP formulations (top-down memo, bottom-up 1D, bottom-up 2D) illustrate the same recurrence. Path reconstruction (cut sequence) is done by storing which first cut produced the maximum.

Method 1 - Naive Recursion (Exponential)

Intuition

Try every first cut length i from 1..n, recursively solving the remainder n - i. This explores a recursion tree where many sub-lengths repeat.

Approach

1. Base: f(0) = 0.
2. Recursive: f(n) = max_{1 ≤ i ≤ n} ( price[i] + f(n - i) ) (assuming 1-indexed price logic; code adapts indexes for 0-based arrays).
3. Return f(n).

Overlapping Subproblems

As you can see repeating subproblems, like 1 and 0.

graph TD;
	A("rod(3)") --- B("rod(2)") & C("rod(1)"):::orange & D("rod(0)"):::purple
	B --- E("rod(1)"):::orange & F("rod(0)"):::purple
	C --- G("rod(0)"):::purple


classDef orange fill:#FFA07A,stroke:#333,stroke-width:2px;
classDef purple fill:#DDA0DD,stroke:#333,stroke-width:2px;

Code

C++

#include <vector>
using namespace std;

long maxRodRevenue(const vector<long>& price, int n) {
  if (n == 0) return 0;
  long best = 0;
  for (int i = 1; i <= n; ++i) { // cut first piece length i
    best = max(best, price[i-1] + maxRodRevenue(price, n - i));
  }
  return best;
}

Go

package main

func maxRodRevenue(price []int64, n int) int64 {
  if n == 0 { return 0 }
  var best int64 = 0
  for i := 1; i <= n; i++ {
    v := price[i-1] + maxRodRevenue(price, n-i)
    if v > best { best = v }
  }
  return best
}

Java

import java.util.*;

class SolutionRec {
  public long maxRodRevenue(List<Long> price, int n) {
    if (n == 0) return 0L;
    long best = 0;
    for (int i = 1; i <= n; i++) {
      best = Math.max(best, price.get(i-1) + maxRodRevenue(price, n - i));
    }
    return best;
  }
}

Python

from typing import List

def maxRodRevenue(price: List[int], n: int) -> int:
  if n == 0:
    return 0
  best = 0
  for i in range(1, n + 1):
    best = max(best, price[i-1] + maxRodRevenue(price, n - i))
  return best

Complexity

• ⏰ Time complexity: O(2^n) – each length spawns branching across cuts, large overlapping subproblems.
• 🧺 Space complexity: O(n) – recursion depth (worst chain of 1-length cuts).

Method 2 - Top-Down Memoization (Stores Best Values + First Cut)

Intuition

Cache results of sub-lengths so each f(len) is computed once. Also store which first cut length gave the best to reconstruct a solution.

Approach

1. Allocate memo of size n+1 initialized to -1 (meaning unknown) and firstCut array.
2. Recursive helper solve(L) returns best revenue for length L:
   • If L == 0 return 0.
   • If cached, return.
   • Iterate i in 1..L: candidate = price[i-1] + solve(L - i); track best & firstCut[L].
3. After computing solve(n), reconstruct the cuts by following firstCut while length > 0.

Code

C++

#include <vector>
#include <algorithm>
using namespace std;

class SolutionTopDownRod {
  vector<long> memo; vector<int> first;
  long dfs(const vector<long>& price, int L) {
    if (L == 0) return 0;
    if (memo[L] != -1) return memo[L];
    long best = 0; int cut = 1;
    for (int i = 1; i <= L; ++i) {
      long val = price[i-1] + dfs(price, L - i);
      if (val > best) { best = val; cut = i; }
    }
    first[L] = cut;
    return memo[L] = best;
  }
public:
  pair<long, vector<int>> maxRodRevenue(const vector<long>& price, int n) {
    memo.assign(n+1, -1); first.assign(n+1, 0);
    long ans = dfs(price, n);
    vector<int> cuts; int L = n;
    while (L > 0) { cuts.push_back(first[L]); L -= first[L]; }
    return {ans, cuts};
  }
};

Go

package main

func maxRodRevenueTopDown(price []int64, n int) (int64, []int) {
  memo := make([]int64, n+1)
  first := make([]int, n+1)
  for i := range memo { memo[i] = -1 }
  var dfs func(int) int64
  dfs = func(L int) int64 {
    if L == 0 { return 0 }
    if memo[L] != -1 { return memo[L] }
    var best int64 = 0
    bestCut := 1
    for i := 1; i <= L; i++ {
      v := price[i-1] + dfs(L-i)
      if v > best { best = v; bestCut = i }
    }
    first[L] = bestCut
    memo[L] = best
    return best
  }
  ans := dfs(n)
  cuts := []int{}
  L := n
  for L > 0 { cuts = append(cuts, first[L]); L -= first[L] }
  return ans, cuts
}

Java

import java.util.*;

class SolutionTopDownRod {
  long[] memo; int[] first;
  long dfs(List<Long> price, int L) {
    if (L == 0) return 0L;
    if (memo[L] != -1) return memo[L];
    long best = 0; int cut = 1;
    for (int i = 1; i <= L; i++) {
      long val = price.get(i-1) + dfs(price, L - i);
      if (val > best) { best = val; cut = i; }
    }
    first[L] = cut;
    return memo[L] = best;
  }
  public Map<String,Object> maxRodRevenue(List<Long> price, int n) {
    memo = new long[n+1]; first = new int[n+1];
    Arrays.fill(memo, -1);
    long ans = dfs(price, n);
    List<Integer> cuts = new ArrayList<>();
    int L = n; while (L > 0) { cuts.add(first[L]); L -= first[L]; }
    Map<String,Object> res = new HashMap<>();
    res.put("revenue", ans); res.put("cuts", cuts); return res;
  }
}

Python

from typing import List, Tuple
from functools import lru_cache

class SolutionTopDownRod:
  def maxRodRevenue(self, price: List[int], n: int) -> Tuple[int, List[int]]:
    if n == 0:
      return 0, []
    first: List[int] = [0]*(n+1)
    @lru_cache(None)
    def dfs(L: int) -> int:
      if L == 0:
        return 0
      best = 0
      cut_choice = 1
      for i in range(1, L+1):
        v = price[i-1] + dfs(L-i)
        if v > best:
          best = v
          cut_choice = i
      first[L] = cut_choice
      return best
    ans = dfs(n)
    cuts: List[int] = []
    L = n
    while L > 0:
      cuts.append(first[L])
      L -= first[L]
    return ans, cuts

Complexity

• ⏰ Time complexity: O(n^2) – for each length L, we iterate through 1..L once (total of 1+2+..+n = n(n+1)/2).
• 🧺 Space complexity: O(n) – memo + recursion stack depth O(n) (chain of 1-length cuts).

Method 3 - Bottom-Up DP (1D Array, Also Tracks Cuts)

Intuition

Iteratively build dp[L] for L = 1..n using previously computed revenues for smaller lengths. Keep a firstCut[L] similar to memoized variant but iteratively.

Approach

1. Initialize dp[0] = 0.
2. For each length L from 1..n:
   • Set best = 0.
   • For each i in 1..L: candidate = price[i-1] + dp[L - i]; update best & record firstCut[L].
   • Store dp[L] = best.
3. Reconstruct cuts by iteratively subtracting firstCut[length] from length.

Code

C++

#include <vector>
using namespace std;

class SolutionRodBU1D {
public:
  pair<long, vector<int>> maxRodRevenue(const vector<long>& price, int n) {
    vector<long> dp(n+1, 0);
    vector<int> first(n+1, 0);
    for (int L = 1; L <= n; ++L) {
      long best = 0; int cut = 1;
      for (int i = 1; i <= L; ++i) {
        long val = price[i-1] + dp[L - i];
        if (val > best) { best = val; cut = i; }
      }
      dp[L] = best; first[L] = cut;
    }
    vector<int> cuts; int L = n;
    while (L > 0) { cuts.push_back(first[L]); L -= first[L]; }
    return {dp[n], cuts};
  }
};

Go

package main

func maxRodRevenueBU1D(price []int64, n int) (int64, []int) {
  dp := make([]int64, n+1)
  first := make([]int, n+1)
  for L := 1; L <= n; L++ {
    var best int64
    cut := 1
    for i := 1; i <= L; i++ {
      v := price[i-1] + dp[L-i]
      if v > best { best = v; cut = i }
    }
    dp[L] = best
    first[L] = cut
  }
  cuts := []int{}
  L := n
  for L > 0 { cuts = append(cuts, first[L]); L -= first[L] }
  return dp[n], cuts
}

Java

import java.util.*;

class SolutionRodBU1D {
  public Map<String,Object> maxRodRevenue(List<Long> price, int n) {
    long[] dp = new long[n+1];
    int[] first = new int[n+1];
    for (int L = 1; L <= n; L++) {
      long best = 0; int cut = 1;
      for (int i = 1; i <= L; i++) {
        long val = price.get(i-1) + dp[L - i];
        if (val > best) { best = val; cut = i; }
      }
      dp[L] = best; first[L] = cut;
    }
    List<Integer> cuts = new ArrayList<>();
    int L = n; while (L > 0) { cuts.add(first[L]); L -= first[L]; }
    Map<String,Object> res = new HashMap<>();
    res.put("revenue", dp[n]); res.put("cuts", cuts); return res;
  }
}

Python

from typing import List, Tuple

class SolutionRodBU1D:
  def maxRodRevenue(self, price: List[int], n: int) -> Tuple[int, List[int]]:
    dp = [0]*(n+1)
    first = [0]*(n+1)
    for L in range(1, n+1):
      best = 0
      cut_choice = 1
      for i in range(1, L+1):
        val = price[i-1] + dp[L-i]
        if val > best:
          best = val
          cut_choice = i
      dp[L] = best
      first[L] = cut_choice
    cuts: List[int] = []
    L = n
    while L > 0:
      cuts.append(first[L])
      L -= first[L]
    return dp[n], cuts

Complexity

• ⏰ Time complexity: O(n^2) – nested loops over L (1..n) and i (1..L).
• 🧺 Space complexity: O(n) – arrays dp, first.

DP Table Progression Example

Example: price = [1, 5, 8, 9, 10, 17, 17, 20] (index i-1 is price of piece length i), n = 8.

We build dp[L] for L = 0..8 and record firstCut[L] (the first cut length chosen for an optimal revenue). dp[0] = 0.

For each length L, we test all first cut lengths i = 1..L and compute candidate: price[i-1] + dp[L - i].

L	Tried (i : price[i-1] + dp[L-i])	Best dp[L]	firstCut[L]	Reason
1	1: 1+0 = 1	1	1	Only option
2	1: 1+1 = 2, 2: 5+0 = 5	5	2	Cut full length 2
3	1: 1+5 = 6, 2: 5+1 = 6, 3: 8+0=8	8	3	Single length 3 piece best
4	1: 1+8=9, 2: 5+5=10, 3: 8+1=9, 4:9+0=9	10	2	Two pieces of length 2
5	1:1+10=11, 2:5+8=13, 3:8+5=13, 4:9+1=10, 5:10+0=10	13	2	First achieving 13 is cut=2
6	1:1+13=14, 2:5+10=15, 3:8+8=16, 4:9+5=14, 5:10+1=11, 6:17+0=17	17	6	Single length 6 piece
7	1:1+17=18, 2:5+13=18, 3:8+10=18, 4:9+8=17, 5:10+5=15, 6:17+1=18, 7:17+0=17	18	1	First 18 encountered at i=1
8	1:1+18=19, 2:5+17=22, 3:8+13=21, 4:9+10=19, 5:10+8=18, 6:17+5=22, 7:17+1=18, 8:20+0=20	22	2	First 22 encountered at i=2

Reconstruction for n = 8:

firstCut[8] = 2  -> remaining 6
firstCut[6] = 6  -> remaining 0
Cuts sequence: [2, 6]  (order of discovery; can also report sorted)
Revenue = dp[8] = 22 ( = price[2-1] + price[6-1] = 5 + 17 )

Key observations:

• Multiple first cuts can yield the same best value (e.g., L = 7); we keep the first encountered for deterministic reconstruction.
• The 1D DP reuses smaller solved lengths directly (dp[L-i]).
• This progression matches the recurrence: dp[L] = max_{1..L} ( price[i-1] + dp[L-i] ).

Method 4 - Bottom-Up 2D DP (Knapsack Style Variant)

Intuition

We can view each piece length i as an item usable multiple times (unbounded knapsack). A 2D table dp[i][L] = best revenue using piece lengths up to i to fill total length L. This is pedagogical; 1D optimized version is preferable.

Approach

1. Let m = n (maximum piece length considered). Build table (m+1) x (n+1) initialized to 0.
2. For i from 1..m (current piece length), for L from 1..n`:
   • If i <= L: dp[i][L] = max( dp[i-1][L], price[i-1] + dp[i][L - i] ) (include multiple times).
   • Else: dp[i][L] = dp[i-1][L].
3. Answer dp[m][n].

Code

C++

#include <vector>
using namespace std;

class SolutionRodBU2D {
public:
  long maxRodRevenue(const vector<long>& price, int n) {
    vector<vector<long>> dp(n+1, vector<long>(n+1, 0));
    for (int i = 1; i <= n; ++i) {
      for (int L = 1; L <= n; ++L) {
        if (i <= L) {
          dp[i][L] = max(dp[i-1][L], price[i-1] + dp[i][L - i]);
        } else {
          dp[i][L] = dp[i-1][L];
        }
      }
    }
    return dp[n][n];
  }
};

Go

package main

func maxRodRevenueBU2D(price []int64, n int) int64 {
  dp := make([][]int64, n+1)
  for i := range dp { dp[i] = make([]int64, n+1) }
  for i := 1; i <= n; i++ {
    for L := 1; L <= n; L++ {
      if i <= L {
        take := price[i-1] + dp[i][L-i]
        skip := dp[i-1][L]
        if take > skip { dp[i][L] = take } else { dp[i][L] = skip }
      } else {
        dp[i][L] = dp[i-1][L]
      }
    }
  }
  return dp[n][n]
}

Java

import java.util.*;

class SolutionRodBU2D {
  public long maxRodRevenue(List<Long> price, int n) {
    long[][] dp = new long[n+1][n+1];
    for (int i = 1; i <= n; i++) {
      for (int L = 1; L <= n; L++) {
        if (i <= L) {
          long take = price.get(i-1) + dp[i][L - i];
          long skip = dp[i-1][L];
          dp[i][L] = Math.max(take, skip);
        } else {
          dp[i][L] = dp[i-1][L];
        }
      }
    }
    return dp[n][n];
  }
}

Python

from typing import List

class SolutionRodBU2D:
  def maxRodRevenue(self, price: List[int], n: int) -> int:
    dp = [[0]*(n+1) for _ in range(n+1)]
    for i in range(1, n+1):
      for L in range(1, n+1):
        if i <= L:
          take = price[i-1] + dp[i][L - i]
          skip = dp[i-1][L]
          dp[i][L] = max(take, skip)
        else:
          dp[i][L] = dp[i-1][L]
    return dp[n][n]

Complexity

• ⏰ Time complexity: O(n^2) – nested over piece length and current length.
• 🧺 Space complexity: O(n^2) – 2D DP table.

Notes

• Any price array indexing must align: price[i-1] corresponds to piece length i.
• If prices are not strictly increasing per length, cutting may outperform selling as one piece.
• For reconstruction, store the first cut or all contributing cuts if multiple optimal decompositions are desired.