Cutting a Rod | DP | A Naive recursive solution for Rod cutting problem ; A utility function to get the maximum of two integers ; Returns the best obtainable price for a rod of length n and price [ ] as prices of different pieces ; Recursively cut the rod in different pieces and compare different configurations ; Driver code
import sys NEW_LINE def max ( a , b ) : NEW_LINE INDENT return a if ( a > b ) else b NEW_LINE DEDENT def cutRod ( price , n ) : NEW_LINE INDENT if ( n <= 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT max_val = - sys . maxsize - 1 NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT max_val = max ( max_val , price [ i ] + cutRod ( price , n - i - 1 ) ) NEW_LINE DEDENT return max_val NEW_LINE DEDENT arr = [ 1 , 5 , 8 , 9 , 10 , 17 , 17 , 20 ] NEW_LINE size = len ( arr ) NEW_LINE print ( " Maximum ▁ Obtainable ▁ Value ▁ is " , cutRod ( arr , size ) ) NEW_LINE