Split array into subarrays at minimum cost by minimizing count of repeating elements in each subarray | Python3 program for the above approach ; Function to find the minimum cost of splitting the array into subarrays ; Get the maximum element ; dp will store the minimum cost upto index i ; Initialize the result array ; Initialise the first element ; Create the frequency array ; Update the frequency ; Counting the cost of the duplicate element ; Minimum cost of operation from 0 to j ; Total cost of the array ; Driver Code ; Given cost K ; Function call
import sys NEW_LINE def findMinCost ( a , k , n ) : NEW_LINE INDENT max_ele = max ( a ) NEW_LINE dp = [ 0 ] * ( n + 1 ) NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT dp [ i ] = sys . maxsize NEW_LINE DEDENT dp [ 0 ] = 0 NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT freq = [ 0 ] * ( max_ele + 1 ) NEW_LINE for j in range ( i , n ) : NEW_LINE INDENT freq [ a [ j ] ] += 1 NEW_LINE cost = 0 NEW_LINE for x in range ( 0 , max_ele + 1 ) : NEW_LINE INDENT cost += ( 0 if ( freq [ x ] == 1 ) else freq [ x ] ) NEW_LINE DEDENT dp [ j + 1 ] = min ( dp [ i ] + cost + k , dp [ j + 1 ] ) NEW_LINE DEDENT DEDENT return dp [ n ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 2 , 1 , 1 , 1 ] ; NEW_LINE K = 2 ; NEW_LINE n = len ( arr ) ; NEW_LINE print ( findMinCost ( arr , K , n ) ) ; NEW_LINE DEDENT