Objective: Given a rod of length n inches and a table of prices p_{i}, i=1,2,…,n, write an algorithm to find the maximum revenue r_{n} obtainable by cutting up the rod and selling the pieces.

This is very good basic problem after fibonacci sequence if you are new to Dynamic programming. We will see how the dynamic programming is used to overcome the issues with recursion(Time Complexity).

Given: Rod lengths are integers and For i=1,2,…,n we know the price p_{i} of a rod of length i inches

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

I was just about to burst laughing any second while the professor was explaining all the details of “rod cutting” in the class. Seriously, why did it have to be a “rod”?

Eugen Daroczy

In the DP solution, since there’s the option of not cutting the rod/rope at any given point, then we should not initialize:
int max = -1;

but use instead the formula below, so we start off using the value of the entire substring. If the cuts add up to more value, that will be the partial solution.
int max = value[i-1];

Similarly, for the recursive problem we need so initialize as:
int max = value[length-1];