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
int dp [ n + 1 ] [ k + 1 ] ; for ( int i = 0 ; i <= n ; i ++ ) for ( int j = 0 ; j <= k ; j ++ ) dp [ i ] [ j ] = inf ;