狗家onsite一道特别的题

题目：M乘以N的二维由1乘1的小方形构成的矩形，可以分解成最少多少个SQAURE。。。

现场给出了一个递归解法，就是无限由长边分解短边，但是自己发现有点bug准备改，可是面试官说没问题这么做是对的开始问下一

游客，本帖隐藏的内容需要积分高于 188 才可浏览，您当前积分为 0。
查看如何攒积分 Click here for more info.

复杂。。。


分享给版上的朋友们。。。

henryoier 发表于 2016-12-13 07:07
我的想法是: 不失一般性，首先假定m > n否则我们将m，n对调，那么枚举边长从1 到 n的正方形去覆盖一个矩形 ...

这种方法的假设是“L的最佳分割法中的某条边界一定能够把L恰好切成两个矩形”。但是这个假设应该并非总是成立的。比如177x176

                               
登录/注册后可看大图

所以此法恐怕不行

我的想法是: 不失一般性，首先假定m > n否则我们将m，n对调，那么枚举边长从1 到 n的正方形去覆盖一个矩形的一个角，那么剩下的L形（如果正方形边长为n那么剩下的是一个矩形）可以有两种分解的方法。那么状态转移方程式为dp(m, n) = min{min{dp(m, n - i) + dp(m - i, i), dp(i, n - i) + dp(m - i, n)} + 1}, 边界条件是m == n, return 1, m或n中有一个为0 return 0

问问： 分解为最少多少个？？
什么意思。
是指最少能分解出多少个，还是最多能分解出多少个。每个小方形都算是一个square吧

递归的解法能详细说下么～

这不leetcode题么

byrlhb 发表于 2016-12-13 07:12
这不leetcode题么

题号是？

蜗牛君 发表于 2016-12-13 07:22
题号是？

sorry 看错了，

henryoier 发表于 2016-12-13 07:07
我的想法是: 不失一般性，首先假定m > n否则我们将m，n对调，那么枚举边长从1 到 n的正方形去覆盖一个矩形 ...

感觉应该是对的

补充内容 (2016-12-13 08:19):
sorry，找到返例了

byrlhb 发表于 2016-12-13 07:51
感觉应该是对的

这是个NP问题...我一个大神同学去面g家最后一轮第一题就是这个他上来先证了个NP，不知道他后来给的解法是什么...

henryoier 发表于 2016-12-13 08:19
这是个NP问题...我一个大神同学去面g家最后一轮第一题就是这个他上来先证了个NP，不知道他后来给的解法是 ...

反例是啥，dp不行吗