I was going through the following question

Given a paper of size A x B. Task is to cut the paper into squares of any size. Find the minimum number of squares that can be cut from the paper.

I tried writing a dp and a greedy solution for this problem, but none of them worked. Unfortunately the site from where I am practising this question also does not have a correct solution. Can someone please suggest a solution to this problem or is this also NP-hard like polygon partition ?

Complete Problem Statement