Divide chocolate bar into pieces , minimizing the area of invalid pieces | Java 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 ; Print minArea as the output ; Driver Code ; Given N & M ; Given valid dimensions ; Function Call
import java . io . * ; import java . util . * ; class GFG { static final int sz = 1001 ; static boolean ok [ ] [ ] = new boolean [ sz ] [ sz ] ; static int dp [ ] [ ] = new int [ sz ] [ sz ] ; static class pair { int first , second ; public pair ( int first , int second ) { this . first = first ; this . second = second ; } } static int minInvalidAreaUtil ( int l , int b ) { if ( dp [ l ] [ b ] == - 1 ) { if ( ok [ l ] [ b ] ) { return dp [ l ] [ b ] = 0 ; } int ans = l * b ; for ( int i = 1 ; i < b ; i ++ ) { ans = Math . min ( ans , minInvalidAreaUtil ( l , i ) + minInvalidAreaUtil ( l , b - i ) ) ; } for ( int i = 1 ; i < l ; i ++ ) { ans = Math . min ( ans , minInvalidAreaUtil ( i , b ) + minInvalidAreaUtil ( l - i , b ) ) ; } dp [ l ] [ b ] = ans ; } return dp [ l ] [ b ] ; } static void minInvalidArea ( int N , int M , Vector < pair > dimensions ) { int K = dimensions . size ( ) ; for ( int i = 0 ; i < K ; i ++ ) { ok [ dimensions . elementAt ( i ) . first ] [ dimensions . elementAt ( i ) . second ] = true ; ok [ dimensions . elementAt ( i ) . second ] [ dimensions . elementAt ( i ) . first ] = true ; } for ( int i = 0 ; i < sz ; i ++ ) { for ( int j = 0 ; j < sz ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } int minArea = minInvalidAreaUtil ( N , M ) ; System . out . println ( minArea ) ; } public static void main ( String [ ] args ) { int N = 10 , M = 10 ; Vector < pair > dimensions = new Vector < > ( ) ; dimensions . add ( new pair ( 3 , 5 ) ) ; minInvalidArea ( N , M , dimensions ) ; } }