c++ - 以最少的正方形切割矩形

Question

我正在尝试解决以下问题:

A rectangular paper sheet of M*N is to be cut down into squares such that:

1. The paper is cut along a line that is parallel to one of the sides of the paper.
2. The paper is cut such that the resultant dimensions are always integers.

The process stops when the paper can't be cut any further.

What is the minimum number of paper pieces cut such that all are squares?

Limits: 1 <= N <= 100 and 1 <= M <= 100.

Example: Let N=1 and M=2, then answer is 2 as the minimum number of squares that can be cut is 2 (the paper is cut horizontally along the smaller side in the middle).

我的代码:

cin >> n >> m;

int N = min(n,m);
int M = max(n,m);
int ans = 0;

while (N != M) {
    ans++;
    int x = M - N;
    int y = N;
    M = max(x, y);
    N = min(x, y);
}

if (N == M && M != 0)
   ans++;

但我不明白这种方法有什么问题，因为它给了我一个错误的答案。

Answer 1

我认为 DP 和贪婪解决方案都不是最优的。以下是 DP 解决方案的反例:

考虑大小为 13 X 11 的矩形。DP 解决方案给出 8 作为答案。但最优解只有 6 个方格。

这个帖子有很多反例:https://mathoverflow.net/questions/116382/tiling-a-rectangle-with-the-smallest-number-of-squares

另外，看看这个以获得正确的解决方案:http://int-e.eu/~bf3/squares/