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)。外层循环变量i0n,内层循环变量ji的基础上依次加上每个整数的完全平方,超过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];
    }
};