Участник:Easik/tiling-a-rectangle-with-the-fewest-squares

Материал из DISCOPAL
Перейти к: навигация, поиск

Python 3

import numpy as np
 
class Solution:
    def tilingRectangle(self, n: int, m: int) -> int:
 
        a, b, c = 14, 13, 11
        self.dp = np.zeros((a, a))
 
        # Calc min squares that cover the tile
        @lru_cache(None)
        def min_squares(m, n):
 
            vert_min = np.inf
            horiz_min = np.inf
 
            # Trivial case with a single square
            if n == m:
                return 1
 
            # Calculation already done
            if self.dp[m][n] != 0:
                return self.dp[m][n]
 
            for i in range(1, int(np.floor(m / 2)) + 1):
                horiz_min = min(horiz_min, min_squares(i, n) + \
                                min_squares(m - i, n))
 
            for i in range(1, int(np.floor(n / 2)) + 1):
                vert_min = min(vert_min, min_squares(m, i) + \
                               min_squares(m, n - i))
 
            self.dp[m][n] = min(vert_min, horiz_min)
 
            return self.dp[m][n]
 
        if ((n == c) & (m == b)) | ((n == b) & (m == c)):
            return int(np.floor(max(b, c) / 2))
        return int(min_squares(n, m))