# 1. Introduction

The *Rod Cutting Problem* is a classic optimization problem that is often solved using dynamic programming. Given a rod of length *n* and a list of prices for different lengths of rods, the objective is to determine the best way to cut the rod into smaller rods to maximize the total selling price. The challenge lies in deciding the lengths of pieces to cut in order to maximize profit.

# 2. Program Steps

1. Initialize an array *val[]* of size *n + 1* where *val[i]* is the maximum value obtainable by cutting up the rod of length *i*.

2. Set *val[0]* to 0. This means a rod of length 0 has no value.

3. For each length *i*, compute *val[i]* by going through all possible cuts and picking the maximum value obtainable.

4. Return *val[n]* as the maximum value obtainable for the rod of length *n*.

# 3. Code Program

```
public class RodCutting {
public static int cutRod(int[] prices, int n) {
int[] val = new int[n + 1];
val[0] = 0;
for (int i = 1; i <= n; i++) {
int max_val = Integer.MIN_VALUE;
for (int j = 0; j < i; j++) {
max_val = Math.max(max_val, prices[j] + val[i - j - 1]);
}
val[i] = max_val;
}
return val[n];
}
public static void main(String[] args) {
int[] prices = {1, 5, 8, 9, 10, 17, 17, 20};
int n = prices.length;
System.out.println("Maximum obtainable value is " + cutRod(prices, n));
}
}
```

### Output:

Maximum obtainable value is 22

# 4. Step By Step Explanation

1. The *cutRod* function takes in *prices* (an array containing the prices of rods for different lengths) and *n* (the total length of the rod) as parameters.

2. The *val* array is initialized to store the maximum value obtainable for each length from *0* to *n*.

3. The outer loop runs from *1* to *n*, representing the current length of the rod being considered.

4. The inner loop runs from *0* to the current length. For each possible cut length, it computes the value obtainable by adding the price of the cut to the best value of the remaining length.

5. After all possible lengths are considered, *val[n]* will contain the maximum value obtainable for the entire rod.

6. In the *main* function, a sample *prices* array is provided, and the *cutRod* function is called to compute the maximum obtainable value.