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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int solve ( string str , int K ) { int n = str . length ( ) ; long long dp [ K ] [ n ] ; memset ( dp , 0 , sizeof dp ) ; if ( n < K ) return -1 ; else if ( n == K ) return 0 ; long 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 ] = INT_MAX ; ones = 0 ; zeroes = 0 ; for ( int k = i ; k >= 0 ; k -- ) { if ( str [ k ] == '0' ) zeroes ++ ; else ones ++ ; dp [ s ] [ i ] = min ( dp [ s ] [ i ] , + ( ( k - 1 >= 0 ) ? ones * zeroes + dp [ s - 1 ] [ k - 1 ] : INT_MAX ) ) ; } } } return ( dp [ K - 1 ] [ n - 1 ] == INT_MAX ) ? -1 : dp [ K - 1 ] [ n - 1 ] ; } int main ( ) { string S = "0101" ; int K = 2 ; cout << solve ( S , K ) << endl ; return 0 ; }