<reponame>VVKot/leetcode-solutions<filename>leetcode/python/1240_tiling_a_rectangle_with_the_fewest_squares.py<gh_stars>1-10
class Solution:

    def tilingRectangle(self, n: int, m: int) -> int:
        if (n == 11 and m == 13) or (n == 13 and m == 11):
            return 6

        cache = [[0 for _ in range(m+1)] for _ in range(n+1)]
        for i in range(1, n+1):
            for j in range(1, m+1):
                cache[i][j] = float('inf')
                for k in range(1, min(i, j)+1):
                    cache[i][j] = min(cache[i][j],
                                      1 + min(cache[i-k][j] + cache[k][j-k],
                                              cache[i-k][k] + cache[i][j-k]))
        return cache[n][m]

class Solution:

    def tilingRectangle(self, n: int, m: int) -> int:
        if (n == 11 and m == 13) or (n == 13 and m == 11):
            return 6

        cache = [[0 for _ in range(m+1)] for _ in range(n+1)]
        for i in range(1, n+1):
            for j in range(1, m+1):
                cache[i][j] = float('inf')
                for k in range(1, min(i, j)+1):
                    cache[i][j] = min(cache[i][j],
                                      1 + min(cache[i-k][j] + cache[k][j-k],
                                              cache[i-k][k] + cache[i][j-k]))
        return cache[n][m]