Задача: 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).
Размещаем этот квадрат в левом верхнем углу и рекурсивно покрываем оставшиеся три части:
Прямоугольник слева от квадрата.
Прямоугольник сверху от квадрата.
Прямоугольник справа и снизу от квадрата.

😎 Решение:

function tilingRectangle($n, $m) {
    $dp = array_fill(0, $n + 1, array_fill(0, $m + 1, PHP_INT_MAX));
    
    for ($i = 1; $i <= min($n, $m); $i++) {
        $dp[$i][$i] = 1;
    }
    
    for ($h = 1; $h <= $n; $h++) {
        for ($w = 1; $w <= $m; $w++) {
            if ($h == $w) continue;
            for ($i = 1; $i <= intdiv($h, 2); $i++) {
                $dp[$h][$w] = min($dp[$h][$w], $dp[$i][$w] + $dp[$h - $i][$w]);
            }
            for ($j = 1; $j <= intdiv($w, 2); $j++) {
                $dp[$h][$w] = min($dp[$h][$w], $dp[$h][$j] + $dp[$h][$w - $j]);
            }
        }
    }
    return $dp[$n][$m];
}

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