Optimally accommodate 0 s and 1 s from a Binary String into K buckets | C ++ implementation of the approach ; 2 - D dp array saving different states dp [ i ] [ j ] = minimum value of accommodation till i 'th index of the string using j+1 number of buckets. ; Function to find the minimum required sum using dynamic programming ; If both start and bucket reached end then return 0 else that arrangement is not possible so return INT_MAX ; Corner case ; If state if already calculated then return its answer ; Start filling zeroes and ones which to be accommodated in jth bucket then ans for current arrangement will be ones * zeroes + recur ( i + 1 , bucket + 1 ) ; If this arrangement is not possible then don 't calculate further ; Function to initialize the dp and call solveUtil ( ) method to get the answer ; Start with 0 - th index and 1 bucket ; Driver code ; K buckets
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < vector < int > > dp ; int solveUtil ( int start , int bucket , string str , int K ) { int N = str . size ( ) ; if ( start == N ) { if ( bucket == K ) return 0 ; return INT_MAX ; } if ( bucket == K ) return INT_MAX ; if ( dp [ start ] [ bucket ] != -1 ) return dp [ start ] [ bucket ] ; int zeroes = 0 ; int ones = 0 ; int ans = INT_MAX ; for ( int i = start ; i < N ; ++ i ) { if ( str [ i ] == '1' ) ones ++ ; else zeroes ++ ; if ( ones * zeroes > ans ) break ; int temp = solveUtil ( i + 1 , bucket + 1 , str , K ) ; if ( temp != INT_MAX ) { ans = min ( ans , temp + ( ones * zeroes ) ) ; } } return dp [ start ] [ bucket ] = ans ; } int solve ( string str , int K ) { int N = str . size ( ) ; dp . clear ( ) ; dp . resize ( N , vector < int > ( K , -1 ) ) ; int ans = solveUtil ( 0 , 0 , str , K ) ; return ans == INT_MAX ? -1 : ans ; } int main ( ) { string S = "0101" ; int K = 2 ; cout << solve ( S , K ) << endl ; return 0 ; }