Partition a given rectangle into minimum no. of squares

general
,
1

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

2

Read about euclid gcd algorithm for details.

Repeat this until B!=0:
Ans += A/B
A, B = B, A%B

Try to prove how. Just see, that i try to make squares of size B, A/B is number of squares i am able to make, and last line counts number of suares required to cover area, which couldnt be covered in squares of side B.

3

This approach is not optimal for all cases

4

you are right… Its not optimal

5

example
30 35
can be decomposed into
20*20 + 15*15 + 15*15 + 10*10 + 10*10

6

for calculating result of
30 35
can we calculate result for
6 7 ?
will it give same results ??

7

Oh
My mistake.

Some sort of DP solution must be there.

1 Like