[leetcode Perfect Squares] 最少完全平

原题：

给定一个正整数n，要求找出最小数量的完全平方数，使得它们的和等于n。

既然是最小的数量，那就是完全平方数需要尽可能大，我的第一反应是能不能使用贪心算法。比如给定数字13，第一个最大的完全平方数是9，还剩下4刚好也是一个完全平方数。那么，贪心算法真的在任何情况下都能使用吗？我们不妨再看一个例子，比如说12：根据贪心原则，第一个最大的完全平方数是9，此时还剩下3，3只能对应3个1。也就是说我们总共用了4个数，但是我们发现12 = 4 + 4 + 4，只需要使用3个数。因此，贪心算法在这里并不适用。

我们不妨先看下如何用暴力的方法来解决它。还是以刚才的数字12为例：第一个数先取9，12减9还剩3，然后继续对3求最小数量的完全平方数。也就是说，我们将原本一个大问题转化为了一个更小的问题，运用了“分而治之”的思想，很容易想到可以使用递归。若一个数取9无法完成，接下来再用4去尝试。找出所有的可行解，并在可行解中返回数量最少的那个。

但是，如果按照这种方式，算法的复杂度将会变得非常大。不知道大家有没有想到在用递归求斐波那契数列的时候，会产生很多冗余的运算。我们可以使用一个数组来保存中间计算的结果。每次递归的时候，若能在数组中找到解，则直接返回，不需要再次运算。在这道题中可以使用类似的方法，我们用dp[i - 1]表示数字i最少需要多少个完全平方数，通过保留状态的方法，这其实就是动态规划。

另外，我们还可以对算法做一个剪枝操作，我们不需要每次从最大的完全平方数一直遍历到1，只要遍历前半部分就可以（为什么？自己想）。比如说数字17，最大的完全平方数是16，我们只需要从4遍历到3即可。

最后，根据上面的分析，我们的代码如下：

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记录当前使用了多少个完全平方数
     */
    int dfs(int n, int count, int *dp) {

        if (n == 0) { //已经数字n分解完，直接返回count
            return count;
        }

        int c = 0;
        if ((c = dp[n - 1]) != 0) { //若在状态数组中能找到解，直接返回，
            return count + c;       //并且还需要加上已经使用的个数
        }
        
        //从所有的解中找出使用数字最少的
        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; //计算完成后，将结果保存到状态数组中
        return res;
    }

};