Consider the following variant of the Rod Cutting problem As

Consider the following variant of the Rod Cutting problem. As we cut the rod. it becomes weaker, so we can only make k

Solution

Naive approach is a recursive one.

In recursive approach we we use the same subRoutine number of times

We have to think of the way we avoid using the same rotine again.

This can be done by storing the previous sub routines into the array.

Below algorithm demonistrates the bottun up dynamic rod cutting ..

BottomUpCutRod(p, n)
store: array(0..n)
store(0) := 0
for j in 1 .. n loop
max_price := MinInt
for i in 1 .. j loop -- Find the max cut position for length j
max_price := max(max_price, price(i) + store(j-i)
end loop
store(j) := max_price
end loop
return r(n)

In the above prgram we use the store array to stre the max price of that perticular cut. we look up for the value in next step. where as in naive approach we caluclate the same price again

In the above algorithm we use only two for loops, which were nested

for i 1 to n

for j 1 to n

the time complexity for one nested loop id O(n^2)

which is way too much lesser than the worst time complexity of the recursive solution.