Clustering / Partitioning an array such that sum of square differences is minimum | Python3 program to find minimum cost k partitions of array . ; Returns minimum cost of partitioning a [ ] in k clusters . ; Create a dp [ ] [ ] table and initialize all values as infinite . dp [ i ] [ j ] is going to store optimal partition cost for arr [ 0. . i - 1 ] and j partitions ; Fill dp [ ] [ ] in bottom up manner ; Current ending position ( After i - th iteration result for a [ 0. . i - 1 ] is computed . ; j is number of partitions ; Picking previous partition for current i . ; Driver code
inf = 1000000000 ; NEW_LINE def minCost ( a , n , k ) : NEW_LINE INDENT dp = [ [ inf for i in range ( k + 1 ) ] for j in range ( n + 1 ) ] ; NEW_LINE dp [ 0 ] [ 0 ] = 0 ; NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( 1 , k + 1 ) : NEW_LINE INDENT for m in range ( i - 1 , - 1 , - 1 ) : NEW_LINE INDENT dp [ i ] [ j ] = min ( dp [ i ] [ j ] , dp [ m ] [ j - 1 ] + ( a [ i - 1 ] - a [ m ] ) * ( a [ i - 1 ] - a [ m ] ) ) ; NEW_LINE DEDENT DEDENT DEDENT return dp [ n ] [ k ] ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT k = 2 ; NEW_LINE a = [ 1 , 5 , 8 , 10 ] ; NEW_LINE n = len ( a ) ; NEW_LINE print ( minCost ( a , n , k ) ) ; NEW_LINE DEDENT