Problem statement

https://leetcode.com/problems/tiling-a-rectangle-with-the-fewest-squares/

Solution

The idea is to keep state: heights in each column. Also keep heuristic: what is minimum number of squares we need if we have left area A. On each step we check first if we can beat heuristic, if not, return. Then find minimum height in histogram and try to put square: left bottom angle of the square must be in this point, but we can try squares of different sizes. Also make sure we did not exceed the top of our rectangle.

Complexity

Time complexity is difficult to estimate, something like exponential I think.

Code

class Solution:
    def tilingRectangle(self, n, m):
        @lru_cache(None)
        def dp(A):
            if A == 0: return 0
            return min(dp(A-k**2) for k in range(1, int(A ** 0.5) + 1))

        def dfs(H, moves, area):
            if moves + dp(m*n - area) >= self.ans: return
            if area == m*n: self.ans = min(self.ans, moves)

            min_height = min(H)
            l = r = H.index(min_height)
            while r + 1 < m and H[r + 1] == min_height:
                r += 1
            for i in range(min(r - l + 1, n - min_height), 0, -1):
                H2 = H[:]
                for j in range(i): H2[l + j] += i
                dfs(H2, moves + 1, area + i*i) 
        
        self.ans = m * n   
        dfs([0] * m, 0, 0)
        return self.ans