Optimally accommodate 0 s and 1 s from a Binary String into K buckets | C # implementation of the approach ; Function to find the minimum required sum using dynamic programming ; dp [ i , j ] = minimum val of accommodation till j 'th index of the string  using i+1 number of buckets.  Final ans will be in dp[n-1, K-1] ; Corner cases ; Filling first row , if only 1 bucket then simple count number of zeros and ones and do the multiplication ; If k = 0 then this arrangement is not possible ; If no arrangement is possible then our answer will remain INT_MAX so return - 1 ; Driver code ; K buckets
using System ; class GFG { static long solve ( string str , int K ) { int n = str . Length ; long [ , ] dp = new long [ K , n ] ; if ( n < K ) return - 1 ; else if ( n == K ) return 0 ; long zeroes = 0 , ones = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( str [ i ] == '0' ) zeroes ++ ; else ones ++ ; dp [ 0 , i ] = ones * zeroes ; } for ( int s = 1 ; s < K ; s ++ ) { for ( int i = 0 ; i < n ; i ++ ) { dp [ s , i ] = Int32 . MaxValue ; ones = 0 ; zeroes = 0 ; for ( int k = i ; k >= 0 ; k -- ) { if ( str [ k ] == '0' ) zeroes ++ ; else ones ++ ; dp [ s , i ] = Math . Min ( dp [ s , i ] , + ( ( k - 1 >= 0 ) ? ones * zeroes + dp [ s - 1 , k - 1 ] : Int32 . MaxValue ) ) ; } } } return ( dp [ K - 1 , n - 1 ] == Int32 . MaxValue ) ? - 1 : dp [ K - 1 , n - 1 ] ; } public static void Main ( string [ ] args ) { string S = "0101" ; int K = 2 ; Console . WriteLine ( solve ( S , K ) ) ; } }