Rod Cutting Problem in DSA Typescript - Build from Scratch

Rod Cutting Problem

📖 Scenario: You have a metal rod of a certain length. You want to cut it into smaller pieces to sell. Each piece has a price depending on its length. Your goal is to find the best way to cut the rod to get the most money.

🎯 Goal: Build a program that calculates the maximum money you can get by cutting the rod into pieces using given prices for each length.

📋 What You'll Learn

Create an array called prices with prices for rod lengths 1 to 8.

Create a variable called rodLength with the value 8.

Create a variable called maxRevenue to store the best money you can get.

Use a loop to calculate the best revenue for each rod length from 1 to rodLength.

Print the maximum revenue for the full rod length.

💡 Why This Matters

🌍 Real World

This problem models how to cut raw materials like metal rods or wood to maximize profit in manufacturing or sales.

💼 Career

Understanding this problem helps in roles involving optimization, dynamic programming, and resource management in software development.

1

Create the prices array

Create an array called prices with these exact values: [1, 5, 8, 9, 10, 17, 17, 20] representing prices for rod lengths 1 to 8.

DSA Typescript

# Your code here

Hint

Use const prices = [1, 5, 8, 9, 10, 17, 17, 20]; to create the array.

2

Set the rod length

Create a variable called rodLength and set it to 8.

DSA Typescript

const prices = [1, 5, 8, 9, 10, 17, 17, 20];
# Your code here

Hint

Use const rodLength = 8; to set the rod length.

3

Calculate maximum revenue

Create a variable called maxRevenue as an array of length rodLength + 1 filled with zeros. Then use a for loop with variable i from 1 to rodLength inclusive. Inside it, use another for loop with variable j from 1 to i inclusive. Update maxRevenue[i] with the maximum of its current value and prices[j - 1] + maxRevenue[i - j].

DSA Typescript

const prices = [1, 5, 8, 9, 10, 17, 17, 20];
const rodLength = 8;
# Your code here

Hint

Use two nested loops to fill maxRevenue with the best prices.

4

Print the maximum revenue

Print the value of maxRevenue[rodLength] using console.log.

DSA Typescript

const prices = [1, 5, 8, 9, 10, 17, 17, 20];
const rodLength = 8;
const maxRevenue = new Array(rodLength + 1).fill(0);
for (let i = 1; i <= rodLength; i++) {
    for (let j = 1; j <= i; j++) {
        maxRevenue[i] = Math.max(maxRevenue[i], prices[j - 1] + maxRevenue[i - j]);
    }
}
# Your code here

Hint

Use console.log(maxRevenue[rodLength]); to print the result.

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