题目1372:
平方求和
时间限制:1000ms
单点时限:1000ms
内存限制:256MB
描述
对于一个非负整数n，最少需要几个完全平方数，使其和为n？
输入
输入包含多组数据。对于每组数据：
第一行是n；如果n为-1，表示输入结束。(0 <= n <= 1000000001)
输出
针对每组数据，输出最少需要的完全平方数。
样例输入
3
4
5
-1
样例输出
3
1
2
解题:
一开始的思路：动态规划
结果：超空间
动态规划是很自然的想法，每个N都可能是一个平方a 和其它平方s的和组成，通过控制平方数a的大小，并利用之前已经得到的答案，选择其中的最小值作为N的答案。
但是很显然，1000000002*sizeof(short)远远超出了空间限制。
不过开始在没有别的好办法的情况下，我还是写了，至少得点基础分吧。
short *table = new short [max_n+1];
table[0]=0;
table[1]=1;
for(int i=2;i<=max_n;i++){
short min_count=table[i-1]+1;
for(int j=1;j*j<=i;j++){
int new_count = table[i-j*j]+1;
if(new_count<min_count)min_count = new_count;
}
table[i]=min_count;
}
苦思冥想后的意外收获：四方定理
一时间没想到好办法，用第一种方法打印了前1000个数的解。如图
非常有规律啊，我不禁猜测可能最大的答案就是4。
然后按图索骥，我找到了
四方定理：
所有自然数至多只要用四个数的平方和就可以表示。
顺便贴一个证明：
改进的思路：位运算
结果：超时间
有了四方定理，可以简化问题，只要不属于1、2、3，答案必定是4无疑。
然后考虑到空间不足。设计了新方案：
使用位运算，数字i能否被分解就由第i位来标记，1个、2个、3个平方和就需要三个变量，分别是once，twice，third
const int MAX_N = 1000000002;
class SpaceArray {
public:
bitset<MAX_N> once;//only for query
bitset<MAX_N> twice;
bitset<MAX_N> third;
};
once时间复杂度： O（根号N）
twice需要once中标记为平方的位数，嵌套两次相加而得，时间复杂度为O(N)
third同理，需要once和twice里位数的和， O（N^(3/2)）
注：把3个变量once、twice、third封装到class里，是为了 new 这个class，这种调用方式是在堆中分配内存，可以很大；相反，直接使用是在栈中调用，会报错-栈空间不够。
顺便复习了一下堆栈的知识，可怜我半吊子的C++水平。
最终的解决
放弃把表里每个值都求出来的思路了，现在只考虑输入的这个N；
采用方法：求根后取整再平方和原值比较。
bool check1(int number) {//是否一个平方组成
int a = int(sqrt(number));
return a*a == number;
}
bool check2(int number) {//是否两个平方和组成
for (int i = 1, i2 = i*i; i2<number; i2+=(2*i+1), i++) {
if (check1(number - i2))return true;
}
return false;
}
bool check3(int number) {//是否三个平方和组成
for (int i = 1, i2 = i*i; i2<number; i2 += (2 * i + 1), i++) {
if (check2(number - i2))return true;
}
return false;
}
根据四方定理，不是以上三者的都属于4个平方和可以组成的。
3个函数求值的时间复杂度如下
O（1）
O（N^1/2）
O（N）
一直WA的原因：0
开始一直以为输入0，输出也应该是0（0个完全平方的和是0）
走投无路，开始想各种可能性。结果这道题把0本身也看成是完全平方，无语。即 0 = 0 * 0,所以答案是1。
