Given two numbers M and N, which represents the length and breadth of a paper, the task is to cut the paper into squares of any size and find the minimum number of squares that can be cut from the paper.
classSolution { int dp[101][101]; inthelper(int n, int m){ if(n == 0or m == 0) return0; if(n == 1) return m; if(m == 1) return n; if(n == m) return1; if(dp[n][m] != -1) return dp[n][m]; int mi = min(n, m); int& res = dp[n][m] = INT_MAX;
for(int i = 1; i <= mi; i++) { res = min({res, 1 + helper(n - i, m) + helper(i, m - i), 1 + helper(n, m - i) + helper(n - i, i) }); }
return res; } public: intminCut(int M, int N){ memset(dp, -1, sizeof dp); returnhelper(N,M); } };