Split a binary string into K subsets minimizing sum of products of occurrences of 0 and 1 | C ++ Program to split a given string into K segments such that the sum of product of occurence of characters in them is minimized ; Function to return the minimum sum of products of occurences of 0 and 1 in each segments ; Store the length of the string ; Not possible to generate subsets greater than the length of string ; If the number of subsets equals the length ; Precompute the sum of products for all index ; Calculate the minimum sum of products for K subsets ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minSumProd ( string S , int K ) { int len = S . length ( ) ; if ( K > len ) return -1 ; if ( K == len ) return 0 ; vector < int > dp ( len ) ; int count_zero = 0 , count_one = 0 ; for ( int j = 0 ; j < len ; j ++ ) { ( S [ j ] == '0' ) ? count_zero ++ : count_one ++ ; dp [ j ] = count_zero * count_one ; } for ( int i = 1 ; i < K ; i ++ ) { for ( int j = len ; j >= i ; j -- ) { count_zero = 0 , count_one = 0 ; dp [ j ] = INT_MAX ; for ( int k = j ; k >= i ; k -- ) { ( S [ k ] == '0' ) ? count_zero ++ : count_one ++ ; dp [ j ] = min ( dp [ j ] , count_zero * count_one + dp [ k - 1 ] ) ; } } } return dp [ len - 1 ] ; } int main ( ) { string S = "1011000110110100" ; int K = 5 ; cout << minSumProd ( S , K ) << ' ' ; return 0 ; }