# Rod Cutting

Given a rod of length **N** inches and an array of prices that contains prices for all pieces of size smaller than **n**. Determine the maximum value obtainable by cutting up the rod and selling the pieces.

Input:
First input line consists of N,
denoting the size of array.
Second line of price of ith length piece.
Output:
Print maximum price that can be obtained by selling the pieces.

**Example:**

Input:
Length of rod: 8
Prices of pieces:
1 5 6 9 12 15 13 20
Output:
maximum price that can be obtained: 20

**Explanation:**

Let us first understand the input format

Each element in the array represent price of length i where i is the index (considering 1-indexing).

So, for the above example:

Price of length 1: 1 (arr[0])
Price of length 2: 5 (arr[1])
Price of length 3: 6 (arr[2])
Price of length 4: 9 (arr[3])
Price of length 5: 12 (arr[4])
Price of length 6: 15 (arr[5])
Price of length 7: 13 (arr[6])
Price of length 8: 20 (arr[7])

Now, the thing is cutting the rod recursively. Like you have to option;

- Cut of ith length and recur for remaining
- Else don't cut of that length.

The recursive function can be written as:

*f(n) = maximum (f(i)+f(n-i)) where 1 ≤ i< n*

In the above example, it's found that if we don't cut into pieces, if we sell the whole rod as 1 piece, then it would maximize profit to 20. All other options will lead to less amount of profit.

Also, if we make 4 pieces of length 2, would have same profit, 20.

Let's convert the above recursion in to dynamic programing.

The sub-problem can be to solve for rod of length

iwhereand we need to store the results of this sub-problems in a array, namely DP1<=i<=nDP[n+1]DP[0]=0as the result for rod length 0 is 0.DP[i]which would be results for rod lengthi(subproblems)DP[i]witharr[i-1]which is the result if we don't cut into smaller pieces and sell the whole rod(piece of length i). The reason behinddp[i]=arr[i-1]notarr[i]because in DP array we are following 1-indexing( like forn=1it'sDP[1]) and for arr we are following 0-indexing(forn=1,arr[0])DP[i]which will be maximum profit for sub problem with lengthiHere we will use the recursive relation mentioned above

To calculate

DP[i],for2≤i≤n,if

iis 1 that follows base case,no more pieces to cut downDP[n]is the final result which is maximum profit for rod lengthn.We could have calculated through the recursive function, but needless to say that the recursion tree would have overlapping sub-problem resulting to exponential time complexity. Hence, we converted the recursion into DP and solved.

C++ Implementation:Output