Paper Cut into Minimum Number of Squares | Set 2 | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX = 300 ; int dp [ MAX ] [ MAX ] ; int minimumSquare ( int m , int n ) { int vertical_min = INT_MAX ; int horizontal_min = INT_MAX ; if ( n == 13 && m == 11 ) return 6 ; if ( m == 13 && n == 11 ) return 6 ; if ( m == n ) return 1 ; if ( dp [ m ] [ n ] ) return dp [ m ] [ n ] ; for ( int i = 1 ; i <= m / 2 ; i ++ ) { horizontal_min = min ( minimumSquare ( i , n ) + minimumSquare ( m - i , n ) , horizontal_min ) ; } for ( int j = 1 ; j <= n / 2 ; j ++ ) { vertical_min = min ( minimumSquare ( m , j ) + minimumSquare ( m , n - j ) , vertical_min ) ; } dp [ m ] [ n ] = min ( vertical_min , horizontal_min ) ; return dp [ m ] [ n ] ; } int main ( ) { int m = 30 , n = 35 ; cout << minimumSquare ( m , n ) ; return 0 ; }