Optimally accommodate 0 s and 1 s from a Binary String into K buckets | 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
let dp ; function solveUtil ( start , bucket , str , K ) { let N = str . length ; if ( start == N ) { if ( bucket == K ) { return 0 ; } return Number . MAX_VALUE ; } if ( bucket == K ) { return Number . MAX_VALUE ; } if ( dp [ start ] [ bucket ] != - 1 ) { return dp [ start ] [ bucket ] ; } let zeroes = 0 ; let ones = 0 ; let ans = Number . MAX_VALUE ; for ( let i = start ; i < N ; ++ i ) { if ( str [ i ] == ' ' ) { ones ++ ; } else { zeroes ++ ; } if ( ones * zeroes > ans ) { break ; } let temp = solveUtil ( i + 1 , bucket + 1 , str , K ) ; if ( temp != Number . MAX_VALUE ) { ans = Math . min ( ans , temp + ( ones * zeroes ) ) ; } } return dp [ start ] [ bucket ] = ans ; } function solve ( str , K ) { let N = str . length ; dp = new Array ( N ) ; for ( let i = 0 ; i < N ; i ++ ) { dp [ i ] = new Array ( K ) ; for ( let j = 0 ; j < K ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } let ans = solveUtil ( 0 , 0 , str , K ) ; return ans == Number . MAX_VALUE ? - 1 : ans ; } let S = " " ; let K = 2 ; document . write ( solve ( S , K ) ) ;