原題：
給定一個正整數(shù)n揣钦，要求找出最小數(shù)量的完全平方數(shù)雳灾，使得它們的和等于n。
既然是最小的數(shù)量冯凹，那就是完全平方數(shù)需要盡可能大谎亩，我的第一反應(yīng)是能不能使用貪心算法。比如給定數(shù)字13宇姚，第一個最大的完全平方數(shù)是9匈庭，還剩下4剛好也是一個完全平方數(shù)。那么浑劳，貪心算法真的在任何情況下都能使用嗎阱持？我們不妨再看一個例子，比如說12：根據(jù)貪心原則魔熏，第一個最大的完全平方數(shù)是9衷咽，此時還剩下3，3只能對應(yīng)3個1蒜绽。也就是說我們總共用了4個數(shù)镶骗，但是我們發(fā)現(xiàn)12 = 4 + 4 + 4，只需要使用3個數(shù)躲雅。因此鼎姊，貪心算法在這里并不適用。
我們不妨先看下如何用暴力的方法來解決它相赁。還是以剛才的數(shù)字12為例：第一個數(shù)先取9相寇，12減9還剩3，然后繼續(xù)對3求最小數(shù)量的完全平方數(shù)噪生。也就是說裆赵，我們將原本一個大問題轉(zhuǎn)化為了一個更小的問題，運(yùn)用了“分而治之”的思想跺嗽，很容易想到可以使用遞歸战授。若一個數(shù)取9無法完成，接下來再用4去嘗試桨嫁。找出所有的可行解植兰，并在可行解中返回?cái)?shù)量最少的那個。
但是璃吧，如果按照這種方式楣导，算法的復(fù)雜度將會變得非常大。不知道大家有沒有想到在用遞歸求斐波那契數(shù)列的時候畜挨，會產(chǎn)生很多冗余的運(yùn)算筒繁。我們可以使用一個數(shù)組來保存中間計(jì)算的結(jié)果噩凹。每次遞歸的時候，若能在數(shù)組中找到解毡咏，則直接返回驮宴，不需要再次運(yùn)算。在這道題中可以使用類似的方法呕缭，我們用dp[i - 1]表示數(shù)字i最少需要多少個完全平方數(shù)堵泽，通過保留狀態(tài)的方法，這其實(shí)就是動態(tài)規(guī)劃恢总。
另外迎罗，我們還可以對算法做一個剪枝操作，我們不需要每次從最大的完全平方數(shù)一直遍歷到1片仿，只要遍歷前半部分就可以（為什么纹安？自己想）。比如說數(shù)字17砂豌，最大的完全平方數(shù)是16钻蔑，我們只需要從4遍歷到3即可。
最后奸鸯，根據(jù)上面的分析咪笑，我們的代碼如下：
class Solution {
public:
int numSquares(int n) {
int dp[n];
memset(dp, 0, n * sizeof(n));
int res = dfs(n, 0, dp);
return res;
}
private:
/*
* 用count記錄當(dāng)前使用了多少個完全平方數(shù)
*/
int dfs(int n, int count, int *dp) {
if (n == 0) { //已經(jīng)數(shù)字n分解完，直接返回count
return count;
}
int c = 0;
if ((c = dp[n - 1]) != 0) { //若在狀態(tài)數(shù)組中能找到解娄涩，直接返回窗怒，
return count + c; //并且還需要加上已經(jīng)使用的個數(shù)
}
//從所有的解中找出使用數(shù)字最少的
int res = INT_MAX;
int j = (int) sqrt(n);
for (int i = j; i >= (j / 2 + 1); i--) {
int num = n - pow(i, 2);
int c = dfs(num, count + 1, dp);
res = min(res, c);
}
dp[n - 1] = res - count; //計(jì)算完成后，將結(jié)果保存到狀態(tài)數(shù)組中
return res;
}
};
