Find minimum adjustment cost of an array | Python3 program to find minimum adjustment cost of an array ; Function to find minimum adjustment cost of an array ; dp [ i ] [ j ] stores minimal adjustment cost on changing A [ i ] to j ; handle first element of array separately ; do for rest elements of the array ; replace A [ i ] to j and calculate minimal adjustment cost dp [ i ] [ j ] ; initialize minimal adjustment cost to INT_MAX ; consider all k such that k >= max ( j - target , 0 ) and k <= min ( M , j + target ) and take minimum ; return minimum value from last row of dp table ; Driver Code
M = 100 NEW_LINE def minAdjustmentCost ( A , n , target ) : NEW_LINE INDENT dp = [ [ 0 for i in range ( M + 1 ) ] for i in range ( n ) ] NEW_LINE for j in range ( M + 1 ) : NEW_LINE INDENT dp [ 0 ] [ j ] = abs ( j - A [ 0 ] ) NEW_LINE DEDENT for i in range ( 1 , n ) : NEW_LINE INDENT for j in range ( M + 1 ) : NEW_LINE INDENT dp [ i ] [ j ] = 100000000 NEW_LINE for k in range ( max ( j - target , 0 ) , min ( M , j + target ) + 1 ) : NEW_LINE INDENT dp [ i ] [ j ] = min ( dp [ i ] [ j ] , dp [ i - 1 ] [ k ] + abs ( A [ i ] - j ) ) NEW_LINE DEDENT DEDENT DEDENT res = 10000000 NEW_LINE for j in range ( M + 1 ) : NEW_LINE INDENT res = min ( res , dp [ n - 1 ] [ j ] ) NEW_LINE DEDENT return res NEW_LINE DEDENT arr = [ 55 , 77 , 52 , 61 , 39 , 6 , 25 , 60 , 49 , 47 ] NEW_LINE n = len ( arr ) NEW_LINE target = 10 NEW_LINE print ( " Minimum ▁ adjustment ▁ cost ▁ is " , minAdjustmentCost ( arr , n , target ) , sep = ' ▁ ' ) NEW_LINE