Paper Cut into Minimum Number of Squares | Set 2 | Python3 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 equal to n and length less than 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
MAX = 300 NEW_LINE dp = [ [ 0 for i in range ( MAX ) ] for i in range ( MAX ) ] NEW_LINE def minimumSquare ( m , n ) : NEW_LINE INDENT vertical_min = 10000000000 NEW_LINE horizontal_min = 10000000000 NEW_LINE if n == 13 and m == 11 : NEW_LINE INDENT return 6 NEW_LINE DEDENT if m == 13 and n == 11 : NEW_LINE INDENT return 6 NEW_LINE DEDENT if m == n : NEW_LINE INDENT return 1 NEW_LINE DEDENT if dp [ m ] [ n ] != 0 : NEW_LINE INDENT return dp [ m ] [ n ] NEW_LINE DEDENT for i in range ( 1 , m // 2 + 1 ) : NEW_LINE INDENT horizontal_min = min ( minimumSquare ( i , n ) + minimumSquare ( m - i , n ) , horizontal_min ) NEW_LINE DEDENT for j in range ( 1 , n // 2 + 1 ) : NEW_LINE INDENT vertical_min = min ( minimumSquare ( m , j ) + minimumSquare ( m , n - j ) , vertical_min ) NEW_LINE DEDENT dp [ m ] [ n ] = min ( vertical_min , horizontal_min ) NEW_LINE return dp [ m ] [ n ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT m = 30 NEW_LINE n = 35 NEW_LINE print ( minimumSquare ( m , n ) ) NEW_LINE DEDENT