【题目】
分正方形问题

有一个M×N（单位：厘米）的长方形（M,N都不大于100），要求把它分成边长是整数厘米的正方形，要求正好分完，并且使分出的正方形个数最少。

我本想用贪心算法做这道题，即每次都分出能分成的最大的正方形，可我发现有些情况就不对。
比如5×6的：
      —— —— —— —— —— —— —— —— —— —— —— ——
     |                                                 |   1×1  |
     |                                                 |         |
                                                        —— ——
     |                                                 |   1×1  |
     |                                                 |         |      
                                                        —— ——
     |                5×5                             |   1×1  |
     |                                                 |         |
                                                        —— ——
     |                                                 |   1×1  |
     |                                                 |         |
                                                        —— ——
     |                                                 |   1×1  |
     |                                                 |         |
      —— —— —— —— —— —— —— —— —— —— —— ——
按我的算法应该分成上图的形状，共6个正方形，可是下图：
      —— —— —— —— —— —— —— —— —— —— —— ——
     |                             |                             |
     |                             |                             |
                                                          
     |           3×3              |         3×3                |
     |                             |                             |
                                              
     |                             |                             |
     |                             |                             |
      —— —— —— —— —— —— —— —— —— —— —— ——                                             
     |                   |                   |                   |
     |                   |                   |                   |  
             2×2                 2×2                2×2
     |                   |                   |                   |
     |                   |                   |                   |
      —— —— —— —— —— —— —— —— —— —— —— ——
却只需要5个正方形。

到底怎么做啊？请各位帮帮我。