參考文章
http://www.cnblogs.com/pk28/p/5827338.html
題目
給一個正整數(shù) n, 找到若干個完全平方數(shù)(比如1, 4, 9, ... )使得他們的和等于 n。你需要讓平方數(shù)的個數(shù)最少。
只需要輸出最少的個數(shù)苗胀。
同時酪碘，還有一個定理:四方定理：所有自然數(shù)至多只要用四個數(shù)的平方和就可以表示禁偎。
該題可以使用動態(tài)規(guī)劃來解：
給定的整數(shù)從1開始增大到n叛买，然后使用一個一維數(shù)組來存儲給定數(shù)需要的平方數(shù)的個數(shù)母截。
后一個狀態(tài)與前一個狀態(tài)的轉換：
//n為給定爽柒，m為從1增長到n
//memo[]為備忘錄
for(int i = 0; i*i <m; i++)
{
memo[i]=min(memo[i], memo[m - i*i] + 1)
}
外部一個循環(huán)m從1到n吴菠，內(nèi)部的狀態(tài)轉換公式為：
min內(nèi)部的始終取值最小的，memo[m - i*i] +1 意思為：
+1表示的是 i*i這個平方數(shù)所占的一項浩村。
剩下的個數(shù)為做葵，之前求出的meme[m - i*i]。
從1到最大的平方數(shù)心墅，挨個減嘗試酿矢，存儲最小值。
變形
這個問題可以轉換為判斷一個數(shù)是幾個平方數(shù)的和怎燥。
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開始調用函數(shù)判斷瘫筐。
