**Algorithm Review**\n\n* Credits to all leetcoders who discussed here. \uD83D\uDE0A\n* Denote the solution of (n, m) as s(n, m). Obviously, s(n, m) = s(m, n).\n* (Conjecture 1) Let F_n be the Fibonacci sequence(1, 1, 2, 3, 5, 8...). We purpose that s(F_k, F_(k+1)) = k where k is a positive integer. If that is true, the greedy algorithm does output the correct answer in this special case. (Currently we have checked the rectangles up to 380 * 380 and no counterexamples have been found.)\n\t* s(5, 8) = s(F_5, F_6) = 5\n\t![image](https://assets.leetcode.com/users/orangezeit/image_1572212430.png)\n* Too-specific solution: Hard-code a 13 * 13 table of results pre-calculated by others\n* Specific (and essentially wrong) solutions: Due to the input scale, we can adapt DP or greedy by handling special cases.\n\t* If we adapt (naive) DP (i.e., only storing information of tiling squares in the sub-problems), we only need to deal with one special case 11 * 13 (or equivalently 13 * 11) where the DP answer does not agree with the correct one.\n\t* If we adapt (naive) greedy (i.e. always cutting off the largest possible square), we need to deal with much more special cases compared with DP. I will argue the pros and cons of two methods in the following code block.\n\t\n\t```cpp\n // (Wrong!) DP, must handle special cases and cannot generalize to any (n, m)\n // Credit: [@xiaogugu](https://leetcode.com/problems/tiling-a-rectangle-with-the-fewest-squares/\n\t// discuss/414246/Java-Straightforward-DP%3A-Top-Down-and-Bottom-up), with modifications\n\t// Time Complexity: O(mn * max(m, n))\n\t// Space Complexity: O(mn)\n\t\n int tilingRectangle(int n, int m) {\n if ((n == 11 && m == 13) || (m == 11 && n == 13))\n\t\t\treturn 6; // DP answer is 8\n int dp[n + 1][m + 1] = {};\n \n for (int i = 1; i <= n; i++)\n for (int j = 1; j <= m; j++){\n if (i == j) {\n dp[i][j] = 1;\n continue;\n }\n dp[i][j] = i * j;\n for (int k = 1; k <= i / 2; k++)\n dp[i][j] = min(dp[i][j], dp[i - k][j] + dp[k][j]);\n for (int k = 1; k <= j / 2; k++)\n dp[i][j] = min(dp[i][j], dp[i][j - k] + dp[i][k]);\n }\n \n return dp[n][m];\n }\n\t\n\t// (Wrong!) greedy, must handle much more special cases and cannot generalize to any (n, m)\n\t// You may wonder why I still apply seemingly less efficient algorithm.\n\t// Since naive DP and greedy are both wrong, we can only\n\t// use them as the upper bounds of the true answers in pruning DFS later.\n\t// DP generates more accurate upper bounds in a slower rate, and\n\t// greedy generates less accurate upper bounds in a faster rate. Here is the trade-off.\n\t\n\t// Hint: The Euclidean Algorithm\n\t// Time Complexity: O(log(min(m, n)))\n\t// Space Complexity: O(log(min(m, n)))\n\t\n int tilingRectangle(int n, int m) {\n\t\tif (n > m) swap(m, n);\n\t\tif (n == 5 && m == 6) return 5; // greedy answer is 6\n\t\tif (n == 5 && m == 11) return 6; // greedy answer is 7\n\t\tif (n == 6 && m == 7) return 5; // greedy answer is 7\n\t\tif (n == 6 && m == 11) return 6; // greedy answer is 7\n\t\tif (n == 6 && m == 13) // ... You get the point.\n\t\n return m == n ? 1 : tilingRectangle(n, m - n) + 1;\n\t}\n\t```\n\t* (Conjecture 2) For any positive integers m and n, we further denote the result generated by DP as dp(m, n) and the result generated by greedy as gd(m, n). We purpose that s(m, n) <= dp(m, n) <= gd(m, n) always holds. It is pretty intuitive but I don\'t know how to prove.\n\t* **[Updated]** It might be tempted to construct a **more sophisticated DP / greedy** (i.e. consider rectangles and L-shapes besides squares). This method will **eventually fail** if you test larger m and n. (Chanllenge me if I am wrong.)\n\t\t* Take case 16 * 17 for example. If you draw the tiles, you will realize that there is a "double-L-shape" (Your method might still work with the detailed categories of L-shapes but this is the signal). Needless to say, as m and n increase, there would be more complex shapes that cannot be filled into any category you designed at first (and that\'s usually when DP and greedy fail), but that is just my intuition.\n\t\t![image](https://assets.leetcode.com/users/orangezeit/image_1572481565.png)\n\t\t\n\t\t* If you are lucky and your codes passed case 16 * 17 (the correct answer is 8), it probabily won\'t pass 82 * 83 (the correct answer is 10). The **lowest-order simple squared square figure** below also visualizes the complex relations of the squares.\n\t\t* (Conjecture 3) This problem cannot be solved by DP or greedy alone.\n* General (true) solution: use DFS / backtracking, start stacking squares from any of the four corners, could be improved by A* search.\n\t* Pruning 1: Try largest possible squares first to prune DFS.\n\t* Pruning 2: Use results generated by (naive) DP or greedy discussed above as smaller upper bounds of true answers.\n\t* After actual testing up to 30 * 30, DP upper bounds work better.\n\t* Visualization of heights\n\t* ![image](https://assets.leetcode.com/users/orangezeit/image_1577235083.png)\n\n\t```cpp\n\tclass Solution {\n\tpublic:\n\t\tint tilingRectangle(int n, int m) {\n\t\t\tif (n == m) return 1;\n\t\t\tif (n > m) swap(n, m);\n\t\t\tint heights[n] = {};\n\n\t\t\tint dp[n + 1][m + 1] = {};\n\n\t\t\tfor (int i = 1; i <= n; i++)\n\t\t\t\tfor (int j = 1; j <= m; j++){\n\t\t\t\t\tif (i == j) {\n\t\t\t\t\t\tdp[i][j] = 1;\n\t\t\t\t\t\tcontinue;\n\t\t\t\t\t}\n\t\t\t\t\tdp[i][j] = i * j;\n\t\t\t\t\tfor (int k = 1; k <= i / 2; k++)\n\t\t\t\t\t\tdp[i][j] = min(dp[i][j], dp[i - k][j] + dp[k][j]);\n\t\t\t\t\tfor (int k = 1; k <= j / 2; k++)\n\t\t\t\t\t\tdp[i][j] = min(dp[i][j], dp[i][j - k] + dp[i][k]);\n\t\t\t\t}\n\n\t\t\tint res(dp[n][m]);\n\t\t\tdfs(n, m, heights, 0, res);\n\t\t\treturn res;\n\t\t}\n\t\t\n\t\t// Credit: [@Charles000](https://leetcode.com/problems/tiling-a-rectangle-with-the-fewest-squares/\n\t\t// discuss/414260/8ms-Memorized-Backtrack-Solution-without-special-case!), with modifications\n\t\t// (a) add DP upper bound\n\t\t// (b) use backtracking and pass array by reference to be memory efficient\n\t\t// (c) other minor changes such as removing redundant variables & rewriting conditions\n\t\t// (d) does not include the skyline record since it does not reduce time complexity significantly in tests\n\t\t// Time Complexity: O(m^n)\n\t\t// Space Complexity: O(n)\n\t\t\n\t\tvoid dfs(const int& n, const int& m, int heights[], int cnt, int& res) {\n\t\t\tif (cnt >= res) return;\n\n\t\t\tint left(0), min_height(m);\n\t\t\tfor (int i = 0; i < n; i++)\n\t\t\t\tif (heights[i] < min_height)\n\t\t\t\t\tmin_height = heights[left = i];\n\n\t\t\tif (min_height == m) {\n\t\t\t\tres = min(cnt, res);\n\t\t\t\treturn;\n\t\t\t}\n\n\t\t\tint right(left);\n\t\t\twhile (right < n && heights[left] == heights[right] && right - left + min_height < m) right++;\n\t\t\t/*\n\t\t\tfor (int i = right; i > left; --i) {\n\t\t\t\tfor (int j = left; j < i; ++j)\n\t\t\t\t\theights[j] += i - left;\n\t\t\t\tdfs(n, m, heights, cnt + 1, res);\n\t\t\t\tfor (int j = left; j < i; ++j)\n\t\t\t\t\theights[j] -= i - left;\n\t\t\t}\n\t\t\t*/\n\t\t\t// Credit: @revaluation\n\t\t\t// plot the biggest possible square to the rectangle\n\t\t\tfor (int i = left; i < right; i++)\n\t\t\t\theights[i] += right - left;\n\n\t\t\tfor (int size = right - left; size >= 1; size--) {\n\t\t\t\tdfs(n, m, heights, cnt + 1, res);\n\n\t\t\t\t// update the rectangle to contain the next smaller square\n\t\t\t\tfor (int i = left; i < left + size - 1; i++)\n\t\t\t\t\theights[i]--;\n\t\t\t\theights[left + size - 1] -= size;\n\t\t\t}\n\t\t}\n\t};\n\t```\n\n**Suggestions on Code Review**\n* [Cheat Table](http://int-e.eu/~bf3/squares/young.txt) from [@lee215](https://leetcode.com/problems/tiling-a-rectangle-with-the-fewest-squares/discuss/414160/Cheat)\'s post\n\n* Focus on **basic solutions** in the cheat table\n\n**Mathematical Review**\n\n*WARNING: LOTS OF DEFINITIONS!*\n\nThis problem is just a special case of a group of problems studied by mathematicians. The first (most classic one) is **squaring the square**, which means we want to partition a square into several (possibly unique, i.e. use every kind of square only once) squares. If we require the uniqueness, it is a **simple (or perfect) squared square**, otherwise it is a **compound squared square**. As for this programming problem, we are **squaring the rectangle**. Since the uniqueness is not required, we try to make a **compound squared rectangle**. Since we can always make one, we are interested in finding the minimum number of squares.\n\nWatch the following video for a nice visualization of squaring squares.\n\nhttps://www.youtube.com/watch?v=NoRjwZomUK0\n\n**Transformation**\n\nBetween 1936 to 1938 at Cambridge University, Brooks, Smith, Stone and Tutte transformed the square tiling into an **equivalent electrical circuit** (also known as **Smith diagram**). From the perspective of computer science, it is equivalent to a **directed acyclic graph with more requirements**. (Maybe there is a jargon that I don\'t know to describe that graph, but I just call it a flowchart.) There are three types of nodes. The first type only has the outflows (denoted as +). The second type only has the inflows (denoted as -). The third type has both outflows and inflows.\n\n![image](https://assets.leetcode.com/users/orangezeit/image_1572211864.png)\n\nFor the examples in this programming problem, we can draw similar graphs / flowcharts.\n\n![image](https://assets.leetcode.com/users/orangezeit/image_1572271808.png)\n\n**Several key observations in the graph**\n\n* The edges represent the squares. (@Prezes) The nodes represent the contiguities of the squares.\n* The sum of the outflows of the node (+) / the sum of the inflows of the node (-) is equal to one side of the rectangle.\n* For each of the nodes in between, the sum of the inflows is equal to the sum of the outflows.\n* For each path from node (+) to node (-), the sum of them is equal to the other side of the rectangle.\n\nMaybe someone who aces in graph theory can apply those properties in actual coding, but that is beyond my programming ability.\n\n**HELL-LEVEL Follow-Ups**\n\n* Could be used as contest problems (in professional ones such as CODE JAM, NOT in Leetcode weekly contests)\n* Solving them may not be impossible because DFS always works. The hardness comes from how we improve the efficiency.\n* Extension 0: (Compound tilting - Count & Display) The compound tilting always exists given any positive integers m and n. More specifically, the number of squares ranges from s(n, m) to (m * n) inclusively. How many unique solutions are there? Return int. Also display them as list[list[int]] where int is the size length of squares. (Hint: count at the end of DFS + skip duplicated ones after rotations)\n* Extension 1: What if we require uniqueness (i.e. each kind can be only used once) , or some degree of uniqueness (i.e. each kind can be used at most k times, we refer that as **semi-simple squaring / cubing / hypercubing** in the following text informally) ?\n\t - Q1.1: (Existence) Given m, n, does there exist a solution? Return true or false. As you are probably aware, unlike the compound tilting, the simple or semi-simple one does not always have a solution. (Hint: DFS + hashset if simple or hashmap if semi-simple)\n\t\t - The (only) lowest-order simple squared square\n\n\t![image](https://assets.leetcode.com/users/orangezeit/image_1572213053.png)\n\n\t- Q1.2: (Count & Display) Given m, n and suppose at least one solution exists, how many unique solutions are there? Return int. Also display them as list[list[int]] where int is the size length of squares. ([OEIS A006983](https://oeis.org/A006983)) (Hint: count at the end of DFS + skip duplicated ones after rotations)\n* Extension 2: What if we generalize the problem to 3 dimensions (**Cubing the cube** or **Cubing the cuboid**) or even higher dimensions (**Hypercubing the hypercube** or **Hypercubing the hypercuboid** \u2013 not sure if that is a legitimate word)? It has been proved that simple cubing cubes and simple hypercubing hypercubes are impossible. What about other situations? Show whether they exist. Count and display them if they exist.\n\n| Existence | simple | semi-simple | compound |\n|:-:|:-:|:-:|:-:|\n| (hyper)cube | Impossible | Indeterminate | Definite |\n| (hyper)cuboid | Indeterminate | Indeterminate | Definite |\n\n| Count & Display | simple | semi-simple | compound |\n|:-:|:-:|:-:|:-:|\n| (hyper)cube | NA | ? | ? |\n| (hyper)cuboid | ? | ? | ? |\n\n**[Updated] Sample Solutions to Follow-Ups**\n\nFeel free to run the program at [here](https://repl.it/@YunfeiLuo/tilingrectanglescuboids)\n\n```cpp\n#include \n#include \n#include \n#include \n#include \n#include \n#include \n\n\nclass Tiles {\nprivate:\n std::map record;\n std::set>> rect_collections;\n int res;\n \n const int dpUpperBound2D(const int& x, const int& y) {\n int dp[x + 1][y + 1];\n memset(dp, 0, (x + 1) * (y + 1) * sizeof(int));\n\n for (int i = 1; i <= x; ++i)\n for (int j = 1; j <= y; ++j) {\n if (i == j) {\n dp[i][j] = 1;\n continue;\n }\n dp[i][j] = i * j;\n for (int k = 1; k <= i / 2; ++k)\n dp[i][j] = std::min(dp[i][j], dp[i - k][j] + dp[k][j]);\n for (int k = 1; k <= j / 2; ++k)\n dp[i][j] = std::min(dp[i][j], dp[i][j - k] + dp[i][k]);\n }\n\n return dp[x][y];\n }\n\n const int dpUpperBound3D(const int& x, const int& y, const int& z) {\n int dp[x + 1][y + 1][z + 1];\n memset(dp, 0, (x + 1) * (y + 1) * (z + 1) * sizeof(int));\n\n for (int i = 1; i <= x; ++i)\n for (int j = 1; j <= y; ++j)\n for (int k = 1; k <= z; ++k) {\n if (i == j && j == k) {\n dp[i][j][k] = 1;\n continue;\n }\n dp[i][j][k] = i * j * k;\n for (int n = 1; n <= i / 2; ++n)\n dp[i][j][k] = std::min(dp[i][j][k], dp[i - n][j][k] + dp[n][j][k]);\n for (int n = 1; n <= j / 2; ++n)\n dp[i][j][k] = std::min(dp[i][j][k], dp[i][j - n][k] + dp[i][n][k]);\n for (int n = 1; n <= k / 2; ++n)\n dp[i][j][k] = std::min(dp[i][j][k], dp[i][j][k - n] + dp[i][j][n]);\n }\n\n return dp[x][y][z];\n }\n\n void dfs2D(const int& x, const int& y, const int& n, int *heights, int cnt, int& ub, const bool& minTiles) {\n\t\t\n if (cnt > ub) return;\n\n\t\tint left(0), min_height(y);\n\t\tfor (int i = 0; i < x; i++)\n\t\t\tif (heights[i] < min_height)\n\t\t\t\tmin_height = *(heights + (left = i));\n\n\t\tif (min_height == y) {\n if (cnt <= ub) {\n int i(0);\n std::vector< std::pair > squares(record.size());\n for (const auto& p: record)\n squares[i++] = std::make_pair(p.first, p.second);\n if (minTiles) rect_collections.clear();\n rect_collections.insert(squares);\n }\n res = std::min(res, cnt);\n if (minTiles) ub = std::min(ub, cnt);\n return;\n\t\t}\n\n\t\tint right(left);\n\t\twhile (right < x && *(heights + left) == *(heights + right) && right - left + min_height < y) right++;\n\n\t\tfor (int i = right; i > left; --i) {\n if (n && record.count(i - left) && record[i - left] == n)\n continue;\n for (int j = left; j < i; ++j)\n *(heights + j) += i - left;\n record[i - left]++;\n dfs2D(x, y, n, heights, cnt + 1, ub, minTiles);\n for (int j = left; j < i; ++j)\n *(heights + j) -= i - left;\n if (!(--record[i - left]))\n record.erase(i - left);\n\t\t}\n\t}\n\n void dfs3D(const int& x, const int& y, const int& z, const int& n, int *heights, int cnt, int& ub, const bool& minTiles) {\n\n if (cnt > ub) return;\n\n int left(0), top(0), min_height(z);\n for (int i = 0; i < x; ++i)\n for (int j = 0; j < y; ++j)\n if (*(heights + i * y + j) < min_height)\n min_height = *(heights + (left = i) * y + (top = j));\n\n if (min_height == z) {\n if (cnt <= ub) {\n int m(0);\n std::vector< std::pair > cubes(record.size());\n for (const auto& p: record)\n cubes[m++] = std::make_pair(p.first, p.second);\n if (minTiles) rect_collections.clear();\n rect_collections.insert(cubes);\n }\n res = std::min(res, cnt);\n if (minTiles) ub = std::min(ub, cnt);\n return;\n }\n\n int right(left), bottom(top);\n while (right < x && bottom < y &&\n *(heights + left * y + top) == *(heights + right * y + top) && *(heights + left * y + top) == *(heights + left * y + bottom) &&\n right - left + min_height < z && bottom - top + min_height < z) {\n \n right++;\n bottom++;\n bool notSame(false);\n for (int i = left + 1; i < right; ++i) {\n for (int j = top + 1; j < bottom; ++j)\n if (*(heights + i * y + j) != *(heights + left * y + top)) {\n notSame = true;\n break;\n }\n if (notSame) break;\n }\n\n if (notSame) {\n right--;\n bottom--;\n break;\n }\n }\n \n for (int i = right; i > left; --i) {\n if (n && record.count(i - left) && record[i - left] == n)\n continue;\n for (int j = left; j < i; ++j)\n for (int k = top; k < top + i - left; ++k)\n *(heights + j * y + k) += i - left;\n record[i - left]++;\n dfs3D(x, y, z, n, heights, cnt + 1, ub, minTiles);\n for (int j = left; j < i; ++j)\n for (int k = top; k < top + i - left; ++k)\n *(heights + j * y + k) -= i - left;\n if (!(--record[i - left]))\n record.erase(i - left);\n }\n }\n\npublic:\n // d: dimension\n // arr[]: lengths of dimensions\n // n: the maximum number of each kind of square / cube to be used\n // if n == 0: compound tiling\n // if n > 0: semi-simple tiling (simple / perfect tiling if n == 1)\n // minTile: true if to find the tiles whose number is minimum, false if to find all tiles\n\tvoid tilingRectangleCuboid(int arr[], size_t d, const int n, const bool minTiles) {\n res = std::accumulate(arr, arr + d, 1, std::multiplies());\n\t\tstd::sort(arr, arr + d);\n\n if (d == 2) {\n int ub(minTiles ? dpUpperBound2D(arr[0], arr[1]) : res), heights[arr[0]];\n memset(heights, 0, arr[0] * sizeof(int));\n dfs2D(arr[0], arr[1], n, (int *)heights, 0, ub, minTiles);\n } else {\n int ub(minTiles ? dpUpperBound3D(arr[0], arr[1], arr[2]) : res), heights[arr[0]][arr[1]];\n memset(heights, 0, arr[0] * arr[1] * sizeof(int));\n dfs3D(arr[0], arr[1], arr[2], n, (int *)heights, 0, ub, minTiles);\n }\n\n if (rect_collections.empty()) {\n std::cout << "No solutions with such requirements.\\n";\n } else {\n \n for (const auto& rect: rect_collections) {\n for (const auto& p: rect)\n std::cout << p.first << ": " << p.second << "\\n";\n std::cout << "--------\\n";\n }\n std::cout << "The minimum number of " << (d == 2 ? "squares" : "cubes") << " is " << res << "\\n";\n }\n\t}\n};\n\nint main() {\n Tiles t;\n int d[2] = {112, 112};\n t.tilingRectangleCuboid(d, 2, 1, false);\n}\n```\n\n**References**\n\n[Wikipedia - Squaring the squares](https://en.wikipedia.org/wiki/Squaring_the_square)\n[Wolfram Math World - Perfect Square Dissection](http://mathworld.wolfram.com/PerfectSquareDissection.html)\n[Squaring the Plane](http://math.smith.edu/~jhenle/stp/stp.pdf)

Tiling a Rectangle with the Fewest Squares

Problem Description

Problem Description

Answer Panel