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.

Practice

1. What is the main goal of the Rod Cutting Problem in algorithms?

easy

A. To count the total number of ways to cut the rod

B. To minimize the number of cuts made on the rod

C. To maximize the total profit by cutting the rod into pieces

D. To find the shortest rod length possible

Solution

1. Step 1: Understand the problem objective

   The rod cutting problem aims to cut a rod into pieces to get the maximum total price from selling those pieces.

2. Step 2: Identify the goal

   The goal is to maximize profit, not minimize cuts or count ways.

3. Final Answer:

   To maximize the total profit by cutting the rod into pieces -> Option C

4. Quick Check:

   Maximize profit = maximize total price [OK]

Hint: Focus on maximizing profit from pieces, not cuts or counts [OK]

Common Mistakes:

• Thinking the goal is to minimize cuts
• Confusing with counting ways to cut
• Assuming shortest rod length is the goal

2. Which of the following TypeScript function signatures correctly represents the rod cutting problem function?

easy

A. function rodCutting(prices: string[], length: number): number

B. function rodCutting(length: number, prices: number[]): void

C. function rodCutting(prices: number[], length: number): string

D. function rodCutting(prices: number[], length: number): number

Solution

1. Step 1: Analyze function parameters and return type

   The function should take an array of prices (number[]) and the rod length (number), returning the maximum profit (number).

2. Step 2: Match correct signature

   function rodCutting(prices: number[], length: number): number matches this: prices array first, length second, returns number.

3. Final Answer:

   function rodCutting(prices: number[], length: number): number -> Option D

4. Quick Check:

   Input: prices array, length; Output: number [OK]

Hint: Function returns max profit as number, inputs are prices array and length [OK]

Common Mistakes:

• Swapping parameter order
• Returning void or string instead of number
• Using wrong parameter types like string[] for prices

3. What is the output of the following TypeScript code for rod cutting?

const prices = [1, 5, 8, 9];
const length = 4;
function rodCutting(prices: number[], n: number): number {
  if (n === 0) return 0;
  let maxVal = -Infinity;
  for (let i = 1; i <= n; i++) {
    maxVal = Math.max(maxVal, prices[i - 1] + rodCutting(prices, n - i));
  }
  return maxVal;
}
console.log(rodCutting(prices, length));

medium

A. 10

B. 9

C. 11

D. 8

Solution

1. Step 1: Understand recursive calls and prices

   Prices for lengths 1 to 4 are [1,5,8,9]. The function tries all cuts and sums prices recursively.

2. Step 2: Calculate max profit for length 4

   Possible cuts:
   - 1 + rodCutting(3) = 1 + 8 = 9
   - 5 + rodCutting(2) = 5 + 5 = 10
   - 8 + rodCutting(1) = 8 + 1 = 9
   - 9 + rodCutting(0) = 9 + 0 = 9
   rodCutting(2) = max(1+rodCutting(1),5+rodCutting(0)) = max(1+1,5+0)=5
   rodCutting(3) = max(1+rodCutting(2),5+rodCutting(1),8+rodCutting(0)) = max(1+5,5+1,8+0)= max(6,6,8)=8
   So max is 10.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Max profit for length 4 = 10 [OK]

Hint: Try all cuts recursively, pick max sum [OK]

Common Mistakes:

• Ignoring recursive calls
• Using wrong indices for prices
• Assuming max is price of full length only

4. Identify the bug in this TypeScript rod cutting function:

function rodCutting(prices: number[], n: number): number {
  if (n <= 0) return 0;
  let maxVal = 0;
  for (let i = 1; i < n; i++) {
    maxVal = Math.max(maxVal, prices[i - 1] + rodCutting(prices, n - i));
  }
  return maxVal;
}

medium

A. Loop should run until i <= n, not i < n

B. Base case should return -Infinity instead of 0

C. prices array indexing is off by one

D. Function should return void, not number

Solution

1. Step 1: Check loop range correctness

   The loop runs from i = 1 to i < n, so it misses the case when i = n (full length cut).

2. Step 2: Fix loop to include full length cut

   Changing loop condition to i <= n ensures all cuts including full length are considered.

3. Final Answer:

   Loop should run until i <= n, not i < n -> Option A

4. Quick Check:

   Include full length cut by i <= n [OK]

Hint: Loop must include full length cut (i <= n) [OK]

Common Mistakes:

• Using i < n misses full rod cut
• Changing base case incorrectly
• Misindexing prices array

5. Given a rod of length 5 and prices array [2, 5, 7, 8, 10], what is the maximum profit using dynamic programming approach?

hard

A. 13

B. 12

C. 14

D. 15

Solution

1. Step 1: Use bottom-up DP to find max profit

   Prices: length 1=2, 2=5, 3=7, 4=8, 5=10.
   Calculate max profit for each length:
   dp[0]=0
   dp[1]=max(2)=2
   dp[2]=max(2+dp[1],5)=max(2+2,5)=5
   dp[3]=max(2+dp[2],5+dp[1],7)=max(2+5,5+2,7)=7
   dp[4]=max(2+dp[3],5+dp[2],7+dp[1],8)=max(2+7,5+5,7+2,8)=max(9,10,9,8)=10
   dp[5]=max(2+dp[4],5+dp[3],7+dp[2],8+dp[1],10)=max(2+10,5+7,7+5,8+2,10)=max(12,12,12,10,10)=12
   Therefore, correct answer is 12.

2. Final Answer:

   12 -> Option B

3. Quick Check:

   DP max profit for length 5 = 12 [OK]

Hint: Use bottom-up DP, check all cuts for max profit [OK]

Common Mistakes:

• Ignoring smaller cuts combinations
• Miscomputing dp array values
• Assuming price of full length is max