Clustering / Partitioning an array such that sum of square differences is minimum | C # 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
using System ; class GFG { static int inf = 1000000000 ; static int minCost ( int [ ] a , int n , int k ) { int [ , ] dp = new int [ n + 1 , k + 1 ] ; for ( int i = 0 ; i <= n ; i ++ ) for ( int j = 0 ; j <= k ; j ++ ) dp [ i , j ] = inf ; dp [ 0 , 0 ] = 0 ; for ( int i = 1 ; i <= n ; i ++ ) for ( int j = 1 ; j <= k ; j ++ ) for ( int 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 ] ; } public static void Main ( ) { int k = 2 ; int [ ] a = { 1 , 5 , 8 , 10 } ; int n = a . Length ; Console . Write ( minCost ( a , n , k ) ) ; } }