我正在尝试解决以下问题:
将一个M＊N的长方形纸张切割成正方形，要求：
- 沿着纸张的一条边平行地切割。
- 切割后的纸张边长必须为整数。
当无法再次切割时，过程停止。
最少需要切割多少次，才能得到全部都是正方形的纸片？
限制条件：1 <= N <= 100 and 1 <= M <= 100。
示例：以N=1和M=2为例，答案为2，因为最少可以切割成2个正方形（在中间沿着较小的边水平切割）。
我的代码：
cin >> n >> m;
int N = min(n,m);
int M = max(n,m);
int ans = 0;
while (N != M) {
ans++;
int x = M - N;
int y = N;
M = max(x, y);
N = min(x, y);
}
if (N == M && M != 0)
ans++;
但我不明白这种方法有什么问题，因为它给了我一个错误的答案。
这个帖子有很多反例：https://mathoverflow.net/questions/116382/tiling-a-rectangle-with-the-smallest-number-of-squares
此外，查看这个正确的解决方案：http://int-e.eu/~bf3/squares/
我会将其编写为一个动态(递归)程序。
编写一个函数尝试在某个位置分割矩形，并对两个部分进行递归调用。尝试所有可能的分割并选择具有最小结果的那个。
基本情况是当两侧相等时，即输入已经是一个正方形时，结果为1。
function min_squares(m, n):
// base case:
if m == n: return 1
// minimum number of squares if you split vertically:
min_ver := min { min_squares(m, i) + min_squares(m, n-i) | i ∈ [1, n/2] }
// minimum number of squares if you split horizontally:
min_hor := min { min_squares(i, n) + min_squares(m-i, n) | i ∈ [1, m/2] }
return min { min_hor, min_ver }
为了提高性能，您可以缓存递归结果：
function min_squares(m, n):
// base case:
if m == n: return 1
// check if we already cached this
if cache contains (m, n):
return cache(m, n)
// minimum number of squares if you split vertically:
min_ver := min { min_squares(m, i) + min_squares(m, n-i) | i ∈ [1, n/2] }
// minimum number of squares if you split horizontally:
min_hor := min { min_squares(i, n) + min_squares(m-i, n) | i ∈ [1, m/2] }
// put in cache and return
result := min { min_hor, min_ver }
cache(m, n) := result
return result
在一个具体的C++实现中，您可以使用int cache[100][100]作为缓存数据结构，因为您的输入大小是有限的。将其作为静态局部变量放置，这样它将自动初始化为零。然后将0解释为“未缓存”（因为它不能是任何输入的结果）。
可能的C++实现：http://ideone.com/HbiFOH
vector.size()）。最小函数应该比较大小并返回较小的向量（您可以使用std::min来提供适当的比较函数，例如[](const vector &a, const vector &b){ return a.size() < b.size(); }）。基本情况变为return { n };即一个具有单个正方形宽度的单元素向量。 - leemes贪心算法并非最优解。在一个6×5的矩形上，它使用了一个5×5的正方形和5个1×1的小正方形。最优解使用了2个3×3的正方形和3个2×2的小正方形。
为了得到最优解，使用动态规划。暴力递归解决方案尝试所有可能的横向和纵向首次切割，以最佳方式递归地切割两个部分。通过缓存(记忆化)每个输入的函数值，我们得到一个多项式时间的动态规划(O(m n max(m, n)))。
这个问题可以通过动态规划来解决。
假设我们有一个宽度为 N 和高度为 M 的矩形。
如果 (N == M)，那么它就是一个正方形，不需要做任何事情。
否则，我们可以将矩形分成两个较小的矩形(N - x, M)和(x,M)，然后可以递归地解决。
同样地，我们也可以将其分成(N, M - x)和(N, x)。
伪代码：
int[][]dp;
boolean[][]check;
int cutNeeded(int n, int m)
if(n == m)
return 1;
if(check[n][m])
return dp[n][m];
check[n][m] = true;
int result = n*m;
for(int i = 1; i <= n/2; i++)
int tmp = cutNeeded(n - i, m) + cutNeeded(i,m);
result = min(tmp, result);
for(int i = 1; i <= m/2; i++)
int tmp = cutNeeded(n , m - i) + cutNeeded(n,i);
result = min(tmp, result);
return dp[n][m] = result;
n 和 m 调用过该函数？如果是，则只需返回存储在数组 dp 中的预计算值。 - Pham Trungdef greedy(m, n):
if m == n:
return 1
if m < n:
m, n = n, m
cuts = 0
while n:
cuts += m/n
m, n = n, m % n
return cuts
print greedy(2, 7)
这是Python中的DP尝试 导入sys
def cache(f):
db = {}
def wrap(*args):
key = str(args)
if key not in db:
db[key] = f(*args)
return db[key]
return wrap
@cache
def squares(m, n):
if m == n:
return 1
xcuts = sys.maxint
ycuts = sys.maxint
x, y = 1, 1
while x * 2 <= n:
xcuts = min(xcuts, squares(m, x) + squares(m, n - x))
x += 1
while y * 2 <= m:
ycuts = min(ycuts, squares(y, n) + squares(m - y, n))
y += 1
return min(xcuts, ycuts)
这本质上是经典的整数或0-1背包问题，可以使用贪心或动态规划方法来解决。您可以参考：解决整数背包问题