参考文章

http://www.cnblogs.com/pk28/p/5827338.html

题目

给一个正整数 n, 找到若干个完全平方数(比如1, 4, 9, ... )使得他们的和等于 n。你需要让平方数的个数最少。

只需要输出最少的个数。

同时，还有一个定理:四方定理：所有自然数至多只要用四个数的平方和就可以表示。

该题可以使用动态规划来解：
给定的整数从1开始增大到n，然后使用一个一维数组来存储给定数需要的平方数的个数。

后一个状态与前一个状态的转换：

//n为给定，m为从1增长到n
//memo[]为备忘录
for(int i = 0; i*i <m; i++)
{
  memo[i]=min(memo[i], memo[m - i*i] + 1)
}

外部一个循环m从1到n，内部的状态转换公式为：
min内部的始终取值最小的，memo[m - i*i] +1 意思为：
+1表示的是 i*i这个平方数所占的一项。
剩下的个数为，之前求出的meme[m - i*i]。

从1到最大的平方数，挨个减尝试，存储最小值。

变形

这个问题可以转换为判断一个数是几个平方数的和。

bool isOne(int n)
{
  int a= sqrt(n);
  return n == a*a;
}

bool isTwo(int n)
{
for(int i = 0; i*i < n;i++)
{
  if(isOne(n - i*i))
  {return true ;}
}
return false;
}

bool isThree(int n)
{
 for(int i = 0; i*i < n ;i++)
  {
    if(isTwo(n  - i*i ))
    {return true;}
  }
  return false;
}

在使用的时候以此从1到3开始调用函数判断。