华为题库已更新至:华为实习&秋招真题题库，请移步。

思路：搜索+剪枝

给定一个 $n*m$ 的矩形，我们需要从中分割出若干个正方形，要求正方形个数最少，求该个数。

这道题初看很容易认为是用分治的做法，通过枚举分割长度将矩形分成两块，分别求两块最少能分割的正方形区域再相加，并不断递归求解。

先详细说明下错误的分治的做法：

假设当前矩形的长宽分别为 $a、b$，且有 $a \gt b$