Rod Cutting Problem in DSA Typescript

Mental Model

We want to cut a rod into pieces to get the most money by selling those pieces. Each piece length has a price, and we try all cuts to find the best total price.

Analogy: Imagine you have a chocolate bar and a price list for each piece size. You want to break the bar into smaller pieces to sell and get the most money possible.

Rod length: 4 units
Prices: [1, 5, 8, 9]
Rod: 1 -> 2 -> 3 -> 4 -> null
Try cuts at each position to maximize total price.

Dry Run Walkthrough

Input: rod length = 4, prices = [1, 5, 8, 9]

Goal: Find the best way to cut the rod of length 4 to get maximum total price.

Step 1: Check if rod length is 0, return 0 (base case)

length=4, max_price=0

Why: If rod length is zero, no cuts or sales possible.

Step 2: Try first cut length=1, price=1 + solve for remaining length=3

length=4, try cut=1, price=1 + max_price(3)

Why: Try cutting first piece of length 1 and solve rest recursively.

Step 3: Try first cut length=2, price=5 + solve for remaining length=2

length=4, try cut=2, price=5 + max_price(2)

Why: Try cutting first piece of length 2 and solve rest recursively.

Step 4: Try first cut length=3, price=8 + solve for remaining length=1

length=4, try cut=3, price=8 + max_price(1)

Why: Try cutting first piece of length 3 and solve rest recursively.

Step 5: Try first cut length=4, price=9 + solve for remaining length=0

length=4, try cut=4, price=9 + max_price(0)

Why: Try cutting whole rod as one piece.

Step 6: Calculate max among all cuts: max(1+max_price(3), 5+max_price(2), 8+max_price(1), 9+0)

max_price(4) = max(1+8, 5+5, 8+1, 9) = 10

Why: Choose the cut that gives maximum total price.

Result:

max_price(4) = 10

Annotated Code

DSA Typescript

class RodCutting {
  prices: number[];

  constructor(prices: number[]) {
    this.prices = prices;
  }

  maxProfit(length: number): number {
    if (length === 0) return 0; // base case: no rod left

    let max_val = -Infinity;

    for (let i = 1; i <= length; i++) {
      // try cutting rod at length i
      const current_val = this.prices[i - 1] + this.maxProfit(length - i);
      if (current_val > max_val) {
        max_val = current_val; // update max if better
      }
    }

    return max_val;
  }
}

// Driver code
const prices = [1, 5, 8, 9];
const rodLength = 4;
const rodCutting = new RodCutting(prices);
const result = rodCutting.maxProfit(rodLength);
console.log(result);

if (length === 0) return 0; // base case: no rod left

stop recursion when rod length is zero

for (let i = 1; i <= length; i++) {

try all possible first cut lengths

const current_val = this.prices[i - 1] + this.maxProfit(length - i);

calculate price for first cut plus best price for remaining rod

if (current_val > max_val) { max_val = current_val; }

keep track of maximum price found

Output

10

Complexity Analysis

Time: O(2^n) because it tries all cut combinations recursively without memoization

Space: O(n) due to recursion call stack depth up to rod length

vs Alternative: Dynamic programming approach reduces time to O(n^2) by storing intermediate results

Edge Cases

rod length = 0

returns 0 immediately, no cuts possible

DSA Typescript

if (length === 0) return 0; // base case: no rod left

rod length = 1

returns price of length 1 piece directly

DSA Typescript

for (let i = 1; i <= length; i++) {

prices array empty or shorter than rod length

may cause undefined price access, should ensure prices cover rod length

DSA Typescript

const current_val = this.prices[i - 1] + this.maxProfit(length - i);

When to Use This Pattern

When asked to maximize profit by cutting or splitting a resource into parts with given prices, use the Rod Cutting pattern because it explores all partitions to find the best total.

Common Mistakes

Mistake: Not handling base case length=0 causing infinite recursion
Fix: Add base case check: if length is 0, return 0

Mistake: Using prices index incorrectly causing off-by-one errors
Fix: Use prices[i - 1] for piece length i to match zero-based indexing

Mistake: Not trying all cut lengths from 1 to length
Fix: Loop i from 1 to length inclusive to try all cuts

Summary

Find the best way to cut a rod to maximize total selling price.

Use when you want to split a resource into parts with different values to get the highest total.

Try all possible first cuts and combine with best solutions for remaining length.