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)

c++

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);
    }
};