Paper Cut into Minimum Number of Squares | Set 2 | Javascript program to find minimum number of squares to cut a paper using Dynamic Programming ; Returns min number of squares needed ; Initializing max values to vertical_min and horizontal_min ; N = 11 & M = 13 is a special case ; If the given rectangle is already a square ; If the answer for the given rectangle is previously calculated return that answer ; The rectangle is cut horizontally and vertically into two parts and the cut with minimum value is found for every recursive call . ; Calculating the minimum answer for the rectangles with width equal to n and length less than m for finding the cut point for the minimum answer ; Calculating the minimum answer for the rectangles with width less than n and length equal to m for finding the cut point for the minimum answer ; Minimum of the vertical cut or horizontal cut to form a square is the answer ; Driver code ; Function call
let dp = new Array ( 300 ) ; for ( let i = 0 ; i < 300 ; i ++ ) { dp [ i ] = new Array ( 300 ) ; for ( let j = 0 ; j < 300 ; j ++ ) { dp [ i ] [ j ] = 0 ; } } function minimumSquare ( m , n ) { let vertical_min = Number . MAX_VALUE ; let horizontal_min = Number . MAX_VALUE ; if ( n == 13 && m == 11 ) return 6 ; if ( m == 13 && n == 11 ) return 6 ; if ( m == n ) return 1 ; if ( dp [ m ] [ n ] != 0 ) return dp [ m ] [ n ] ; for ( let i = 1 ; i <= parseInt ( m / 2 , 10 ) ; i ++ ) { horizontal_min = Math . min ( minimumSquare ( i , n ) + minimumSquare ( m - i , n ) , horizontal_min ) ; } for ( let j = 1 ; j <= parseInt ( n / 2 , 10 ) ; j ++ ) { vertical_min = Math . min ( minimumSquare ( m , j ) + minimumSquare ( m , n - j ) , vertical_min ) ; } dp [ m ] [ n ] = Math . min ( vertical_min , horizontal_min ) ; return dp [ m ] [ n ] ; } let m = 30 , n = 35 ; document . write ( minimumSquare ( m , n ) ) ;