We can get the best price by making a cut at different positions and comparing the values obtained after a cut. We can recursively call the same function for a piece obtained after a cut. Let cutRod(n) be the required (best possible price) value for a rod of length n. cutRod(n) can be written as follows. cutRod(n) = max(price[i] + cutRod(n-i-1)) for all i in {0, 1 .. n-1}
We can get the best price by making a cut at different positions and comparing the values obtained after a cut. We can recursively call the same function for a piece obtained after a cut. Let cutRod(n) be the required (best possible price) value for a rod of length n. cutRod(n) can be written as follows. cutRod(n) = max(price[i] + cutRod(n-i-1)) for all i in {0, 1 .. n-1}