Given a rectangle of size n x m, find the minimum number of integer-sided squares that tile the rectangle.
Example 1:
Input: n = 2, m = 3
Output: 3
Explanation: 3 squares are necessary to cover the rectangle.
2 (squares of 1x1)
1 (square of 2x2)
Example 2:
Input: n = 5, m = 8
Output: 5
Example 3:
Input: n = 11, m = 13
Output: 6
Constraints:
1 <= n <= 13
1 <= m <= 13
from functools import lru_cache
import numpy as np

class Solution:
    def __init__(self):
        self.cache={}
        self.res=np.inf
        
    def tilingRectangle(self, n: int, m: int) -> int:
        def tilingRectangleCalc(state, cnt):
            if cnt>self.res:
                return
            state=list(state)
            minHeight=min(state)
            if minHeight==n:
                self.res=min(self.res,cnt)
                return
            minIdx=state.index(minHeight)
            maxL=1
            while minIdx+maxL-1<=m-1 and state[minIdx+maxL-1]==minHeight:
                maxL+=1
            for l in range(maxL-1,0,-1):
                if minHeight+l>n:
                    continue
                s=tuple(state[:minIdx]+[minHeight+l]*l+state[minIdx+l:])
                if s in self.cache and self.cache[s]<cnt+1:
                    continue
                self.cache[s]=cnt+1
                tilingRectangleCalc(s,cnt+1)
            return
        if m>n:
            n,m=m,n
        tilingRectangleCalc(tuple([0]*m),0)   
        return self.res


# class Solution:
#     def tilingRectangle(self, n: int, m: int) -> int:
#         @lru_cache(None)
#         def tilingRectangleCalc(state):
#             state=list(state)
#             minHeight=min(state)
#             if minHeight==n:
#                 return 0
#             minIdx=state.index(minHeight)
#             res=np.inf
#             for l in range(1,n-minHeight+1):
#                 if minIdx+l-1>m-1 or state[minIdx+l-1]>minHeight:
#                     break
#                 res=min(res,tilingRectangleCalc(tuple(state[:minIdx]+\\
#                                                       [minHeight+l]*l+state[minIdx+l:])))
#             return 1+res
#         if m>n:
#             n,m=m,n
#         return tilingRectangleCalc(tuple([0]*m))     


from functools import lru_cache
import numpy as np

class Solution:
    def __init__(self):
        self.cache={}
        self.res=np.inf
        
    def tilingRectangle(self, n: int, m: int) -> int:
        def tilingRectangleCalc(state, cnt):
            if cnt>self.res:
                return
            state=list(state)
            minHeight=min(state)
            if minHeight==n:
                self.res=min(self.res,cnt)
                return
            minIdx=state.index(minHeight)
            maxL=1
            while minIdx+maxL-1<=m-1 and state[minIdx+maxL-1]==minHeight:
                maxL+=1
            for l in range(maxL-1,0,-1):
                if minHeight+l>n:
                    continue
                s=tuple(state[:minIdx]+[minHeight+l]*l+state[minIdx+l:])
                if s in self.cache and self.cache[s]<cnt+1:
                    continue
                self.cache[s]=cnt+1
                tilingRectangleCalc(s,cnt+1)
            return
        if m>n:
            n,m=m,n
        tilingRectangleCalc(tuple([0]*m),0)   
        return self.res


# class Solution:
#     def tilingRectangle(self, n: int, m: int) -> int:
#         @lru_cache(None)
#         def tilingRectangleCalc(state):
#             state=list(state)
#             minHeight=min(state)
#             if minHeight==n:
#                 return 0
#             minIdx=state.index(minHeight)
#             res=np.inf
#             for l in range(1,n-minHeight+1):
#                 if minIdx+l-1>m-1 or state[minIdx+l-1]>minHeight:
#                     break
#                 res=min(res,tilingRectangleCalc(tuple(state[:minIdx]+\\
#                                                       [minHeight+l]*l+state[minIdx+l:])))
#             return 1+res
#         if m>n:
#             n,m=m,n
#         return tilingRectangleCalc(tuple([0]*m))     

