我将其编写为动态（递归）程序。
编写一个试图在某个位置分割矩形的函数。递归调用两个部分的函数。尝试所有可能的分割，并以最小的结果进行分割。
基本情况是当两边相等时，即输入已经是一个正方形，在这种情况下，结果为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 ++实现中，
intcache[100][100]由于输入大小受到限制，因此可以用于缓存数据结构。将其作为静态局部变量放置，因此它将自动用零初始化。然后将0解释为“未缓存”（因为它不可能是任何输入的结果）。
可能的C ++实现：http :
//ideone.com/HbiFOH
