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 of1x1
)1
(square of2x2
)
Example 2:
Input: n = 5, m = 8 Output: 5
Example 3:
Input: n = 11, m = 13 Output: 6
Solution1: DP + Cheating
DP can not handle case 3, for m, n <= 13, (11,13) is the only case of that special case.
dp[i][j] := min squares to tile a i x j rectangle.
dp[i][i] = 1
dp[i][j] = min(dp[r][j] + dp[i-r][j], dp[i][c] + dp[i][j – c]), 1 <= r <= i/2, 1 <= c <= j /2
answer dp[m][n]
Time complexity: O(m*n*max(n, m))
Space complexity: O(m*n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua class Solution { public: int tilingRectangle(int n, int m) { if (max(n, m) == 13 && min(n, m) == 11) return 6; vector<vector<int>> dp(n + 1, vector<int>(m + 1)); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) { dp[i][j] = INT_MAX; if (i == j) { dp[i][j] = 1; continue; } for (int r = 1; r <= i / 2; ++r) dp[i][j] = min(dp[i][j], dp[r][j] + dp[i - r][j]); for (int c = 1; c <= j / 2; ++c) dp[i][j] = min(dp[i][j], dp[i][c] + dp[i][j - c]); } return dp[n][m]; } }; |
Solution 2: DFS
C++
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 |
// Author: Huahua class Solution { public: int tilingRectangle(int n, int m) { if (n > m) return tilingRectangle(m, n); int ans = n * m; vector<int> h(n); function<void(int)> dfs = [&](int cur) { if (cur >= ans) return; auto it = min_element(begin(h), end(h)); if (*it == m) { // All filled ans = cur; return; } int low = *it; int s = it - begin(h); int e = s; // Find the base while (e < n && h[e] == h[s] && (e - s + 1 + low) <= m) ++e; for (int i = --e; i >= s; --i) { // Try all possible square sizes in reverse order. int size = i - s + 1; for (int j = s; j <= i; ++j) h[j] += size; dfs(cur + 1); for (int j = s; j <= i; ++j) h[j] -= size; } }; dfs(0); return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment