Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
recursion + cache solution in Clear category for Cut Into Squares by kdim
from functools import cache
from math import inf
@cache
def cut_into_squares(w: int, h: int) -> int:
if max(w, h) % min(w, h) == 0:
return max(w, h) // min(w, h) - 1
m = inf
for i in range(1, w // 2 + 1):
m = min(m, cut_into_squares(i, h) + cut_into_squares(w - i, h))
for i in range(1, h // 2 + 1):
m = min(m, cut_into_squares(w, i) + cut_into_squares(w, h - i))
return m + 1
Jan. 12, 2024
Comments: