问题：

给定长宽m,n的矩形，将其划分为多个正方形，最少能划分多少个。

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

Example 1:

Example 2:

 

Example 3:

 

 

解法：DP（动态规划）Backtracking（回溯算法）

参考：LeetCode讲解

将问题划分为子问题：

将当前n*m的矩形划分方法：

方法1: 一分为二：

←正方形 [n*n] + →矩形rec [n*(m-n)] 

 

res=dp(rec) + 1(左边正方形)

 

方法2:

↙️正方形 [s*s] + ↗️正方形 [k*k]

+↖️矩形rec_1 [(n-s)*(m-k)] + ↘️矩形rec_2 [(n-k)*(m-s)]  + middle小矩形rec_3 [(k-(n-s))*((m-s)-k)]

变化范围：

s：最大：n ～ 最小：0

k：最大：min((m-s)横, n高) ～ 最小：超过(n-s)高b虚线

res=dp(rec_1)+dp(rec_2)+dp(rec_3) + 2(两个正方形)

 

 

 

 base case：（我们确定n<=m）

• m==0 | | n==0 -> 0 不存在方块
• m==n -> 1 恰好一个正方形
• n==1 -> m 只能分成m个正方形

代码参考：

 1 class Solution {
 2 public:
 3     int count = 0;
 4     void print_intend() {
 5         for(int i=0; i<count; i++) {
 6             printf("  ");
 7         }
 8         return;
 9     }
10     vector<vector<int>> dp;
11     int dfs(int n, int m) {//dfs(short,long)
12         if(n>m) swap(n,m);
13         print_intend();
14         printf("n:%d m:%d\n", n,m);
15         //if (n,m) has been solved
16         if(dp[n][m]!=-1) {
17             print_intend();
18             printf("return dp[n][m]:%d\n", dp[n][m]);
19             return dp[n][m];
20         }
21         //base case:
22         // 1.m=0 || n=0
23         if(m==0 || n==0) {
24             print_intend();
25             printf("return 0\n");
26             return 0;
27         }
28         // 2.n=m -> square
29         if(m==n) {
30             print_intend();
31             printf("return 0\n");
32             return 1;
33         }
34         // 3.n=1 -> m squares
35         if(n==1) {
36             print_intend();
37             printf("return m:%d\n", m);
38             return m;
39         }
40         
41         count++;
42         //other case: res=min(case_1,case2...)
43           //case_1: cut rec to left(square) & right subrec (cause:n<m, ignore up & down)
44         int res = dfs(n,m-n) + 1;
45           //case_2: cut rec to 
46           //left-down(square) & right-up(square) [BLUE] s*s & k*k
47           //left-up(rec_1) & right-down(rec_2) & middle(rec_3) [RED][GREEN][YELLOW]
48           //(n-s)*(m-k)    & (m-s)*(n-k)       & (k-(n-s))*((m-s)-k)
49         int rec_1, rec_2, rec_3;
50         int ans = INT_MAX;
51         for(int s=n-1; s>0; s--) {
52             for(int k=min(n,m-s); k>=n-s; k--) {
53                 rec_1 = dfs(n-s, m-k);
54                 rec_2 = dfs(m-s, n-k);
55                 rec_3 = dfs(k-(n-s), (m-s)-k);
56                 ans = min(ans,rec_1+rec_2+rec_3+2);
57             }
58         }
59         res = min(res, ans);
60         dp[n][m] = res;
61         print_intend();
62         printf("return ans_res:%d, dp[%d][%d]\n", res, n, m);
63         count--;
64         return res;
65     }
66     
67     
68     int tilingRectangle(int n, int m) {
69         int x = min(n,m);//short
70         int y = max(n,m);//long
71         int res;
72         //initialize dp:
73         //dp[0][0]~dp[n+1][m+1] -> all cell = -1
74         dp.resize(x+1);
75         for(auto& d:dp) {
76             d.resize(y+1, -1);
77         }
78         res = dfs(x,y);//dfs(short,long)
79         return res;
80     }
81 };