Divide chocolate bar into pieces , minimizing the area of invalid pieces | Python3 program for the above approach ; Store valid dimensions ; Stores memoization ; Utility function to calculate minimum invalid area for Chocolate piece having dimension ( l , r ) ; Check whether current piece is valid or not If it is , then return zero for current dimension ; Making all possible horizontal cuts , one by one and calculating the sum of minimum invalid area for both the resulting pieces ; Making all possible vertical cuts , one by one and calculating the sum of minimum invalid area for both the resulting pieces ; Store the computed result ; Function to calculate minimum invalid area for Chocolate piece having dimension ( l , r ) ; Total number of valid dimensions ; Storing valid dimensions as for every ( x , y ) both ( x , y ) and ( y , x ) are valid ; Fill dp [ ] [ ] table with - 1 , indicating that results are not computed yet ; Stores minimum area ; PrminArea as the output ; Driver Code ; Given N & M ; Given valid dimensions ; Function Call
sz = 1001 NEW_LINE ok = [ [ 0 for i in range ( sz ) ] for i in range ( sz ) ] NEW_LINE dp = [ [ 0 for i in range ( sz ) ] for i in range ( sz ) ] NEW_LINE def minInvalidAreaUtil ( l , b ) : NEW_LINE INDENT global dp , ok NEW_LINE if ( dp [ l ] [ b ] == - 1 ) : NEW_LINE INDENT if ( ok [ l ] [ b ] ) : NEW_LINE INDENT dp [ l ] [ b ] = 0 NEW_LINE return dp [ l ] [ b ] NEW_LINE DEDENT ans = l * b NEW_LINE for i in range ( 1 , b ) : NEW_LINE INDENT ans = min ( ans , minInvalidAreaUtil ( l , i ) + minInvalidAreaUtil ( l , b - i ) ) NEW_LINE DEDENT for i in range ( 1 , l ) : NEW_LINE INDENT ans = min ( ans , minInvalidAreaUtil ( i , b ) + minInvalidAreaUtil ( l - i , b ) ) NEW_LINE DEDENT dp [ l ] [ b ] = ans NEW_LINE DEDENT return dp [ l ] [ b ] NEW_LINE DEDENT def minInvalidArea ( N , M , dimensions ) : NEW_LINE INDENT global dp , ok NEW_LINE K = len ( dimensions ) NEW_LINE for i in range ( K ) : NEW_LINE INDENT ok [ dimensions [ i ] [ 0 ] ] [ dimensions [ i ] [ 1 ] ] = 1 NEW_LINE ok [ dimensions [ i ] [ 1 ] ] [ dimensions [ i ] [ 0 ] ] = 1 NEW_LINE DEDENT for i in range ( sz ) : NEW_LINE INDENT for j in range ( sz ) : NEW_LINE INDENT dp [ i ] [ j ] = - 1 NEW_LINE DEDENT DEDENT minArea = minInvalidAreaUtil ( N , M ) NEW_LINE print ( minArea ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N , M = 10 , 10 NEW_LINE dimensions = [ [ 3 , 5 ] ] NEW_LINE minInvalidArea ( N , M , dimensions ) NEW_LINE DEDENT