Consider the following variant of the Rod Cutting problem As

Consider the following variant of the Rod Cutting problem. As we cut get the rod, it becomes weaker, so we can only make K < n cuts, where n is the length of the rod. Thus now k, n and the price array P[1 : n] are inputs to the problem. Give an efficient dynamic programming solution for this problem, and analyze its running time.

Solution

Step 1: Base case: If n=0 return 0

Srep 2: Recursively cut the rod in different pieces and compare different configuration.

means follow this recursivly and return max value

cutRod(n) = max(price[i] + cutRod(n-i-1)) for all i in {0, 1 .. n-1}

Time Complexity of the above implementation is O(n^2) as we are recursively folowing the loop