Minimize Cost to reduce the Array to a single element by given operations | Python3 program for the above approach ; Function to minimize the cost to add the array elements to a single element ; Check if the value is already stored in the array ; Compute left subproblem ; Compute left subproblem ; Calculate minimum cost ; Store the answer to avoid recalculation ; Function to generate the cost using Prefix Sum Array technique ; Function to combine the sum of the two subproblems ; Driver Code ; Initialise dp array ; Preprocessing the array
inf = 10000000 NEW_LINE def minCost ( a , i , j , k , prefix , dp ) : NEW_LINE INDENT if ( i >= j ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( dp [ i ] [ j ] != - 1 ) : NEW_LINE INDENT return dp [ i ] [ j ] NEW_LINE DEDENT best_cost = inf NEW_LINE for pos in range ( i , j ) : NEW_LINE INDENT left = minCost ( a , i , pos , k , prefix , dp ) NEW_LINE right = minCost ( a , pos + 1 , j , k , prefix , dp ) NEW_LINE best_cost = min ( best_cost , left + right + ( k * Combine ( prefix , i , j ) ) ) NEW_LINE DEDENT dp [ i ] [ j ] = best_cost NEW_LINE return dp [ i ] [ j ] NEW_LINE DEDENT def preprocess ( a , n ) : NEW_LINE INDENT p = [ 0 ] * n NEW_LINE p [ 0 ] = a [ 0 ] NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT p [ i ] = p [ i - 1 ] + a [ i ] NEW_LINE DEDENT return p NEW_LINE DEDENT def Combine ( p , i , j ) : NEW_LINE INDENT if ( i == 0 ) : NEW_LINE INDENT return p [ j ] NEW_LINE DEDENT else : NEW_LINE INDENT return p [ j ] - p [ i - 1 ] NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 4 NEW_LINE a = [ 4 , 5 , 6 , 7 ] NEW_LINE k = 3 NEW_LINE dp = [ [ - 1 for x in range ( n + 1 ) ] for y in range ( n + 1 ) ] NEW_LINE prefix = preprocess ( a , n ) NEW_LINE print ( minCost ( a , 0 , n - 1 , k , prefix , dp ) ) NEW_LINE DEDENT