Сложность: 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).
Размещаем этот квадрат в левом верхнем углу и рекурсивно покрываем оставшиеся три части:
Прямоугольник слева от квадрата.
Прямоугольник сверху от квадрата.
Прямоугольник справа и снизу от квадрата.
😎 Решение:
def minSquares(n, m):
if n == 0 or m == 0:
return 0
if n == m:
return 1
memo = {}
def solve(n, m):
if (n, m) in memo:
return memo[(n, m)]
if n == 0 or m == 0:
return 0
if n == m:
return 1
min_squares = float('inf')
for i in range(1, min(n, m) + 1):
min_squares = min(min_squares, 1 + solve(n - i, m) + solve(n, m - i) - solve(n - i, m - i))
memo[(n, m)] = min_squares
return min_squares
return solve(n, m)
Ставь 👍 и забирай 📚 Базу знаний