Optimally accommodate 0 s and 1 s from a Binary String into K buckets | Java 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
import java . io . * ; import java . util . * ; class GFG { static int [ ] [ ] dp ; static int solveUtil ( int start , int bucket , String str , int K ) { int N = str . length ( ) ; if ( start == N ) { if ( bucket == K ) { return 0 ; } return Integer . MAX_VALUE ; } if ( bucket == K ) { return Integer . MAX_VALUE ; } if ( dp [ start ] [ bucket ] != - 1 ) { return dp [ start ] [ bucket ] ; } int zeroes = 0 ; int ones = 0 ; int ans = Integer . MAX_VALUE ; for ( int i = start ; i < N ; ++ i ) { if ( str . charAt ( i ) == '1' ) { ones ++ ; } else { zeroes ++ ; } if ( ones * zeroes > ans ) { break ; } int temp = solveUtil ( i + 1 , bucket + 1 , str , K ) ; if ( temp != Integer . MAX_VALUE ) { ans = Math . min ( ans , temp + ( ones * zeroes ) ) ; } } return dp [ start ] [ bucket ] = ans ; } static int solve ( String str , int K ) { int N = str . length ( ) ; dp = new int [ N ] [ K ] ; for ( int [ ] row : dp ) { Arrays . fill ( row , - 1 ) ; } int ans = solveUtil ( 0 , 0 , str , K ) ; return ans == Integer . MAX_VALUE ? - 1 : ans ; } public static void main ( String [ ] args ) { String S = "0101" ; int K = 2 ; System . out . println ( solve ( S , K ) ) ; } }