[Geeks for Geeks] Min cut Square

Min cut Square

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.

  • Time : O(nm)
  • Space : O(nm)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
int dp[101][101];
int helper(int n, int m) {
if(n == 0 or m == 0) return 0;
if(n == 1) return m;
if(m == 1) return n;
if(n == m) return 1;
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:
int minCut(int M, int N) {
memset(dp, -1, sizeof dp);
return helper(N,M);
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/15/PS/GeeksforGeeks/min-cut-square/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.