Minimum cuts on a rectangle to make into squares

Question

I'm trying to solve this problem:

Given an a×b rectangle, your task is to cut it into squares. On each move you can select a rectangle and cut it into two rectangles in such a way that all side lengths remain integers. What is the minimum possible number of moves?

My logic is that the minimum number of cuts means the minimum number of squares; I don't know if it's the correct approach.

I see which side is smaller, Now I know I need to cut bigSide/SmallSide of cuts to have squares of smallSide sides, then I am left with SmallSide and bigSide%smallSide. Then I go on till any side is 0 or both are equal.

#include <iostream>

int main() {
    int a, b; std::cin >> a >> b; // sides of the rectangle

    int res = 0;

    while (a != 0 && b != 0) {
        if (a > b) {
            if (a % b == 0)
                res += a / b - 1;
            else
                res += a / b;
            a = a % b;
        } else if (b > a) {
            if (b % a == 0)
                res += b / a - 1;
            else
                res += b / a;
            b = b % a;
        } else {
            break;
        }
    }

    std::cout << res;

    return 0;
}

When the input is 404 288, my code gives 18, but the right answer is actually 10.

What am I doing wrong?

Answer 1

The current answer is a good start, especially the suggestions to use memoization or dynamic programming, and potentially efficient enough.
Obviously, all answerers used the first with a sub-par data-structure. Vector-of-Vector has much space and performance overhead, using a (strict) lower triangular matrix stored in an array is much more efficient.
Using the maximum value as sentinel (easier with unsigned) would also reduce complexity.
Finally, let's move to dynamic programming instead of memoization to simplify and get even more efficient:

#include <algorithm>
#include <memory>
#include <utility>

constexpr unsigned min_cuts(unsigned a, unsigned b) {
    if (a < b)
        std::swap(a, b);
    if (a == b || !b)
        return 0;
    const auto triangle = [](std::size_t n) { return n * (n - 1) / 2; };
    const auto p = std::make_unique_for_overwrite<unsigned[]>(triangle(a));
    /* const! */ unsigned zero = 0;
    const auto f = [&](auto a, auto b) -> auto& {
        if (a < b)
            std::swap(a, b);
        return a == b ? zero : p[triangle(a - 1) + b - 1];
    };
    for (auto i = 1u; i <= a; ++i) {
        for (auto j = 1u; j < i; ++j) {
            auto r = -1u;
            for (auto k = i / 2; k; --k)
                r = std::min(r, f(k, j) + f(i - k, j));
            for (auto k = j / 2; k; --k)
                r = std::min(r, f(k, i) + f(j - k, i));
            f(i, j) = ++r;
        }
    }
    return f(a, b);
}

Answer 2

It seems clear to me that the problem defines each move as cutting a rectangle to two rectangles along the integer lines, and then asks for the minimum number of such cuts. As you can see there is a clear recursive nature in this problem. Once you cut a rectangle to two parts, you can recurse and cut each of them into squares with minimum moves and then sum up the answers. The problem is that the recursion might lead to exponential time complexity which leads us directly do dynamic programming. You have to use memoization to solve it efficiently (worst case time O(a*b*(a+b))) Here is what I'd suggest doing:

#include <iostream>
#include <vector>
using std::vector;

int min_cuts(int a, int b, vector<vector<int> > &mem) {
    int min = mem[a][b];
    // if already computed, just return the value
    if (min > 0)
        return min;
    // if one side is divisible by the other, 
    // store min-cuts in 'min'
    if (a%b==0)
        min= a/b-1;
    else if (b%a==0)
        min= b/a -1;
    // if there's no obvious solution, recurse
    else {
        // recurse on hight
        for (int i=1; i<a/2; i++) {
            int m = min_cuts(i,b, mem);
            int n = min_cuts(a-i, b, mem);
            if (min<0 or m+n+1<min)
                min = m + n + 1;
        }
        // recurse on width
        for (int j=1; j<b/2; j++) {
            int m = min_cuts(a,j, mem);
            int n = min_cuts(a, b-j, mem);
            if (min<0 or m+n+1<min)
                min = m + n + 1;
        }
    }
    mem[a][b] = min;
    return min;
}

int main() {
    int a, b; std::cin >> a >> b; // sides of the rectangle

    // -1 means the problem is not solved yet, 
    vector<vector<int> > mem(a+1, vector<int>(b+1, -1));
    int res = min_cuts(a,b,mem);
    std::cout << res << std::endl;

    return 0;
}

The reason the foor loops go up until a/2 and b/2 is that cuting a paper is symmetric: if you cut along vertical line i it is the same as cutting along the line a-i if you flip the paper vertically. This is a little optimization hack that reduces complexity by a factor of 4 overall. Another little hack is that by knowing that the problem is that if you transpose the paper the result is the same, meaining min_cuts(a,b)=min_cuts(b,a) you can potentially reduce computations by half. But any major further improvement, say a greedy algorithm would take more thinking (if there exists one at all).