Cutting a Rod | DP | A Dynamic Programming solution for Rod cutting problem ; Returns the best obtainable price for a rod of length n and price [ ] as prices of different pieces ; Build the table val [ ] in bottom up manner and return the last entry from the table ; Driver program to test above functions
INT_MIN = - 32767 NEW_LINE def cutRod ( price , n ) : NEW_LINE INDENT val = [ 0 for x in range ( n + 1 ) ] NEW_LINE val [ 0 ] = 0 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT max_val = INT_MIN NEW_LINE for j in range ( i ) : NEW_LINE INDENT max_val = max ( max_val , price [ j ] + val [ i - j - 1 ] ) NEW_LINE DEDENT val [ i ] = max_val NEW_LINE DEDENT return val [ n ] NEW_LINE DEDENT arr = [ 1 , 5 , 8 , 9 , 10 , 17 , 17 , 20 ] NEW_LINE size = len ( arr ) NEW_LINE print ( " Maximum ▁ Obtainable ▁ Value ▁ is ▁ " + str ( cutRod ( arr , size ) ) ) NEW_LINE