参考文章
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开始调用函数判断。
