Optimally accommodate 0 s and 1 s from a Binary String into K buckets | Python3 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]  Initialise dp with all states as 0 ; 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
import sys NEW_LINE def solve ( Str , K ) : NEW_LINE INDENT n = len ( Str ) NEW_LINE dp = [ [ 0 for i in range ( n ) ] for j in range ( K ) ] NEW_LINE if ( n < K ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT elif ( n == K ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT zeroes = 0 NEW_LINE ones = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( Str [ i ] == '0' ) : NEW_LINE INDENT zeroes += 1 NEW_LINE DEDENT else : NEW_LINE INDENT ones += 1 NEW_LINE DEDENT dp [ 0 ] [ i ] = ones * zeroes NEW_LINE DEDENT for s in range ( 1 , K ) : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT dp [ s ] [ i ] = sys . maxsize NEW_LINE ones = 0 NEW_LINE zeroes = 0 NEW_LINE for k in range ( i , - 1 , - 1 ) : NEW_LINE INDENT if ( Str [ k ] == '0' ) : NEW_LINE INDENT zeroes += 1 NEW_LINE DEDENT else : NEW_LINE INDENT ones += 1 NEW_LINE DEDENT temp = 0 NEW_LINE if ( k - 1 >= 0 ) : NEW_LINE INDENT temp = ones * zeroes + dp [ s - 1 ] [ k - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT temp = sys . maxsize NEW_LINE DEDENT dp [ s ] [ i ] = min ( dp [ s ] [ i ] , temp ) NEW_LINE DEDENT DEDENT DEDENT if ( dp [ K - 1 ] [ n - 1 ] == sys . maxsize ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT else : NEW_LINE INDENT return dp [ K - 1 ] [ n - 1 ] NEW_LINE DEDENT DEDENT S = "0101" NEW_LINE K = 2 NEW_LINE print ( solve ( S , K ) ) NEW_LINE