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

1
2
3


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

1
2
3


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

1
2
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)

1
2
3


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

Base: f(0) = 0.
Recursive: f(n) = max_{1 ≤ i ≤ n} ( price[i] + f(n - i) ) (assuming 1-indexed price logic; code adapts indexes for 0-based arrays).
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


#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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


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;
  }
}

1
2
3
4
5
6
7
8
9


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

Allocate memo of size n+1 initialized to -1 (meaning unknown) and firstCut array.
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].
After computing solve(n), reconstruct the cuts by following firstCut while length > 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


#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};
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


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

Initialize dp[0] = 0.
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.
Reconstruct cuts by iteratively subtracting firstCut[length] from length.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


#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};
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


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:

1
2
3
4


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

Let m = n (maximum piece length considered). Build table (m+1) x (n+1) initialized to 0.
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].
Answer dp[m][n].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


#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];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


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]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


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];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


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.

Problem#

Details#

Examples#

Example 1#

Example 2#

Example 3#

Example 4 (Edge)#

Solution#

Method 1 - Naive Recursion (Exponential)#

Intuition#

Approach#

Overlapping Subproblems#

Code#

Complexity#

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

Intuition#

Approach#

Code#

Complexity#

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

Intuition#

Approach#

Code#

Complexity#

DP Table Progression Example#

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

Intuition#

Approach#

Code#

Complexity#

Notes#

Problem

Details

Examples

Example 1

Example 2

Example 3

Example 4 (Edge)

Solution

Method 1 - Naive Recursion (Exponential)

Intuition

Approach

Overlapping Subproblems

Code

Complexity

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

Intuition

Approach

Code

Complexity

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

Intuition

Approach

Code

Complexity

DP Table Progression Example

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

Intuition

Approach

Code

Complexity

Notes