Задача: 1240. Tiling a Rectangle with the Fewest Squares
Сложность: hard

Если задан прямоугольник размером n x m, верните минимальное количество квадратов с целочисленными сторонами, которые покрывают этот прямоугольник.

Пример:

Input: n = 2, m = 3
Output: 3

👨‍💻 Алгоритм:

1⃣Инициализация рекурсивной функции:
Функция принимает размеры прямоугольника n x m.

2⃣Базовый случай:
Если n = 0 или m = 0, возвращаем 0, так как не осталось пространства для покрытия.

3⃣Рекурсивный случай:
Находим наибольший возможный квадрат, который может быть размещен в текущем прямоугольнике. Это квадрат со стороной min(n, m).
Размещаем этот квадрат в левом верхнем углу и рекурсивно покрываем оставшиеся три части:
Прямоугольник слева от квадрата.
Прямоугольник сверху от квадрата.
Прямоугольник справа и снизу от квадрата.

😎 Решение:

var tilingRectangle = function(n, m) {
    let dp = Array.from({ length: n + 1 }, () => Array(m + 1).fill(Number.MAX_SAFE_INTEGER));
    
    for (let i = 1; i <= Math.min(n, m); i++) {
        dp[i][i] = 1;
    }
    
    for (let h = 1; h <= n; h++) {
        for (let w = 1; w <= m; w++) {
            if (h === w) continue;
            for (let i = 1; i <= h / 2; i++) {
                dp[h][w] = Math.min(dp[h][w], dp[i][w] + dp[h - i][w]);
            }
            for (let j = 1; j <= w / 2; j++) {
                dp[h][w] = Math.min(dp[h][w], dp[h][j] + dp[h][w - j]);
            }
        }
    }
    return dp[n][m];
};

Ставь 👍 и забирай 📚 Базу знаний