# 1240. Tiling a Rectangle with the Fewest Squares  • Time: $O(\max(n, m) \cdot 2^{\max(n, m)})$
• Space: $O(\max(n, m) \cdot 2^{\max(n, m)})$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 class Solution { public: int tilingRectangle(int n, int m) { return tilingRectangle(n, m, 0, vector(m)); } private: static constexpr int kBase = 13; unordered_map dp; int tilingRectangle(int n, int m, long hashedHeights, vector&& heights) { if (const auto it = dp.find(hashedHeights); it != dp.cend()) return it->second; const auto it = ranges::min_element(heights); const int minHeight = *it; if (minHeight == n) // All filled. return 0; int ans = m * n; const int start = it - heights.begin(); // Try to put square of different size that doesn't exceed the width/height. for (int sz = 1; sz <= min(m - start, n - minHeight); ++sz) { // heights[start:start + sz] must has the same height. if (heights[start + sz - 1] != minHeight) break; // Put a square of size sz to cover heights[start:start + sz]. for (int i = start; i < start + sz; ++i) heights[i] += sz; ans = min(ans, tilingRectangle(n, m, hash(heights), move(heights))); for (int i = start; i < start + sz; ++i) heights[i] -= sz; } return dp[hashedHeights] = 1 + ans; } long hash(const vector& heights) { long hashed = 0; for (int i = heights.size() - 1; i >= 0; --i) hashed = hashed * kBase + heights[i]; return hashed; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 class Solution { public int tilingRectangle(int n, int m) { return tilingRectangle(n, m, 0, new int[m]); } private static final int kBase = 13; private Map dp = new HashMap<>(); private int tilingRectangle(int n, int m, long hashedHeights, int[] heights) { if (dp.containsKey(hashedHeights)) return dp.get(hashedHeights); final int minHeight = Arrays.stream(heights).min().getAsInt(); if (minHeight == n) // All filled. return 0; int ans = m * n; int start = -1; for (int i = 0; i < m; ++i) if (heights[i] == minHeight) { start = i; break; } // Try to put square of different size that doesn't exceed the width/height. for (int sz = 1; sz <= Math.min(m - start, n - minHeight); ++sz) { // heights[start:start + sz] must has the same height> if (heights[start + sz - 1] != minHeight) break; // Put a square of size sz to cover heights[start:start + sz]> for (int i = start; i < start + sz; ++i) heights[i] += sz; ans = Math.min(ans, tilingRectangle(n, m, hash(heights), heights)); for (int i = start; i < start + sz; ++i) heights[i] -= sz; } dp.put(hashedHeights, 1 + ans); return 1 + ans; } private long hash(int[] heights) { long hashed = 0; for (int i = heights.length - 1; i >= 0; --i) hashed = hashed * kBase + heights[i]; return hashed; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution: def tilingRectangle(self, n: int, m: int) -> int: @functools.lru_cache(None) def dp(heights: int) -> int: minHeight = min(heights) if minHeight == n: # All filled. return 0 ans = m * n heightsList = list(heights) start = heightsList.index(minHeight) # start index # Try to put square of different size that doesn't exceed the width/height. for sz in range(1, min(m - start + 1, n - minHeight + 1)): # heights[start:start + sz] must has the same height. if heights[start + sz - 1] != minHeight: break # Put a square of size sz to cover heights[start:start + sz]. heightsList[start:start + sz] = [minHeight + sz] * sz ans = min(ans, dp(tuple(heightsList))) return 1 + ans return dp(tuple( * m))