Hey coder. We are going to start with a new question, "Rod Cutting" in this article.

We first want you to go through the problem to understand its outline better.

**Important Link : ** Problem Link, Solution Video Link

ROD CUTTING

Hey coder. We are going to start with a new question, "Rod Cutting" in this article.

We first want you to go through the problem to understand its outline better.

**Important Link : ** Problem Link, Solution Video Link

Understanding Problem

- You are given an integer N, which represents the length of a rod, and an array of integers, which represents the prices of rod pieces of length varying from 1 to N.
- You have to find the maximum value that can be obtained by selling the rod.
- You can sell it in pieces or as a whole.

Say the input array is [1, 5, 8, 9, 10, 17, 17, 20] of size 8 and a rod of length 8.

The above figure shows that a piece of rod of length 1 has a price 1, a piece of rod of length 2 has a price 5, a piece of rod of length 3 has a price 8, and so on.

Hence some of the ways of selling the rod are:

- 1-1-1-1-1-1-1-1
- 2-2-2-2
- 2-3-3

Approach

What

There are 2 strategies for making trees for this problem.** 1. CUT STRATEGY :**

- We make a dp array of the length 9 as shown in figure 2.
- The marked cell denotes the maximum price possible by cutting a rod of length 5 and the original array on top denotes the original prices.
- Since the smallest problem is at length 0, therefore we start solving from there and move up to the length 8.
- We know that for length 0 the maximum price possible is 0.
- Also, according to the given array of numbers, for length 1, the maximum price is 1.
- See in figure 2, we have tweaked our original array such that it is of length 9 such that for length 1, the index is 1 instead of index 0 and further for the rest of the elements.
- A rod of length 2 can be cut as 1-1 or simply remain as 2. The prices for them are 1+1=2 and 5 respectively. We have to choose the maximum selling price, which is why we store 5 against the length 2.
- Now, we move to length 3.

Figure 3 shows that there are 3 ways possible for a length 3.

- We can directly sell the rod of 3 length for price 8.
- We can sell the rod of length 1 for the original price 1 and the other cut piece of length 2, for its maximum price 5.
- Similarly, we can sell the rod of length 2 for the original price 5 and the other cut piece of length 1, for its maximum price 1.

Out of the 3 cases, the maximum selling price is 8.

- For a rod of length 4, the ways are denoted in figure 4.
- We want you to solve the rest of the dp on your own and check your result with figure 5.
- From Figure 5, we get the answer that for the rod of length 8, the maximum selling price is 22.

From this we find out the maximum possible way 2-2 which is equal to 10.

If you face any difficulties in solving this dp array you can also watch the solution video.

We summarize all the trees till length 6 in figure shown.

Here, the numbers along the edge denote the price from the original array and the numbers at the vertices marked with star denote the optimized dp array price.

2. LEFT-RIGHT STRATEGY :

Another way of making trees for rod cutting is given in figure shown below.

- For n=2, we cut the rod into two halves of length 1 each. Hence, the left half
of the rod interacts with the right half as a Cartesian product.

So, one of the ways for n=2 is obtained by adding 1 to the previous result of n=1 and the other way is the original price of 2 itself. -
Similarly, for n=3, half of 3 is 1. Hence, the rod is cut into 1*2. Since the result
for n=1 and n=2 interact with each other, we get the number of ways for n=3
as shown in the figure.
For n=3, it is enough to write 1*2. The result of 2*1 is not required because it
will give the same answer as 1*2.

Also, one of the ways is the original price of 3 itself. - For n=4, we cut the left half of 1 as well as of 2. When 1 is the left half then the rod is cut as 1*3 and when 2 is the left half the rod is cut as 2*2. The result obtained by these 2 interactions is given in the figure.
- The same process is followed for the rest of the lengths too.
- In case you face any difficulties in this problem, we suggest you watch the solution video.
- For a rod of length 0 and 1, the number of ways are 0 and 1 respectively.
- Now, for length 2, there are 2 ways :
- This method is followed by all the other lengths and is shown in figure 9.
- In case you have any difficulties in understanding the dp array for this strategy, we suggest you watch the solution video .

We now discuss the method of filling the dp array using left-right strategy.

The storage, meaning and direction is the same as it was in the cut strategy.

We have an option of selecting the best price for length 1 added to itself versus the best price of length 2. Hence out of price 2 and 5, we select 2.

Out of all the prices in figure 10, the maximum price is 22. Hence, it is our final answer.

**Code**

We write the code of this program using the left-right strategy.

We want you to write it yourself first and then refer to the code given below.

import java.io.*;
import java.util.*;
public class Main {
public static int solution(int[] prices) {
int[]np=new int[prices.length+1];
for(int i=0;i< prices.length;i++){
np[i+1]=prices[i];
}
int[]dp=new int[np.length];
dp[0]=0;
dp[1]=np[1];
for(int i=2;i< dp.length;i++){
dp[i]=np[i];
int li=1;
int ri=i-1;
while(li<=ri){
if(dp[li]+dp[ri]>dp[i]){
dp[i]=dp[li]+dp[ri];
}
li++;
ri--;
}
}
return dp[dp.length-1];
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int[] prices = new int[n];
for (int i = 0; i < n; i++) {
prices[i] = scn.nextInt();
}
System.out.println(solution(prices));
}
}

java; true";

Analysis

Time Complexity O(n)

Space Complexity O(1)

With this we conclude our discussion. We hope you were able to understand it
clearly.

If you still have any doubts you can just watch its solution video.

We'll see you in the next question. Goodbye.