Clustering / Partitioning an array such that sum of square differences is minimum | Javascript 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
let inf = 1000000000 ; function minCost ( a , n , k ) { let dp = new Array ( n + 1 ) ; for ( let i = 0 ; i <= n ; i ++ ) { dp [ i ] = new Array ( k + 1 ) ; for ( let j = 0 ; j <= k ; j ++ ) dp [ i ] [ j ] = inf ; } dp [ 0 ] [ 0 ] = 0 ; for ( let i = 1 ; i <= n ; i ++ ) for ( let j = 1 ; j <= k ; j ++ ) for ( let m = i - 1 ; m >= 0 ; m -- ) dp [ i ] [ j ] = Math . min ( dp [ i ] [ j ] , dp [ m ] [ j - 1 ] + ( a [ i - 1 ] - a [ m ] ) * ( a [ i - 1 ] - a [ m ] ) ) ; return dp [ n ] [ k ] ; } let k = 2 ; let a = [ 1 , 5 , 8 , 10 ] ; let n = a . length ; document . write ( minCost ( a , n , k ) ) ;