Dynamic Programming - Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

题目翻译：
给出一个正整数n，求至少需要多少个完全平方数（例如1，4，9，16……）相加能得到n。
例如，给出n = 12，返回3，因为12 = 4 + 4 + 4。给出n = 13，返回2，因为13 = 4 + 9。

题目分析：
乍一看题目，比较天真的想法是，先从不大于n的最大的完全平方数开始组合，如果和超过了n，就换小一点的完全平方数。但问题是，最后如果凑不齐的话，只能添加很多1，总量上就不是最少的了。例如12，题目中给的例子是4+4+4，需要3个完全平方数。如果从最大的开始组合，那么是9+1+1+1，需要4个完全平方数。

从另一个角度来想，用穷举法来求解就是把不大于n的所有可能的完全平方数的组合都算出来，然后找出和为n的组合中数量最少的那种组合。如果不大于n的完全平方数有m个的话，这个方法的时间复杂度是O(m^m)。显然穷举法时间复杂度过大，不是可行的方法。观察到，在枚举的过程中，有一些组合显然不是最优的，比如把12拆成12个1相加。另外，如果我们能够记录已经找到的最小组合，那么稍大一些的数只需要在此基础上添加若干个完全平方数即可。这里面就包含了动态规划的思想。

具体来说，我们用一个数组来记录已有的结果，初始化为正无穷(INT_MAX)。外层循环变量i从0到n，内层循环变量j在i的基础上依次加上每个整数的完全平方，超过n的不算。那么i + j*j这个数需要的最少的完全平方数的数量，就是数组中当前的数值，和i位置的数值加上一，这两者之间较小的数字。如果当前的值较小，说明我们已经找到过它需要的完全平方数的个数（最初都是正无穷）。否则的话，说明在i的基础上加上j的平方符合条件，所需的完全平方数的个数就是i需要的个数加上一。

代码如下

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 0; i <= n; i++) {
            for (int j = 1; i + j * j <= n; j++) {
                dp[i + j * j] = min(dp[i + j * j], dp[i] + 1);
            }
        }
        return dp[n];
    }
};