279.完全平方数

2020-05-19

题目

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:
1
2
3
输入: n = 12
输出: 3 
解释: 12 = 4 + 4 + 4.
示例 2:
1
2
3
输入: n = 13
输出: 2
解释: 13 = 4 + 9.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/perfect-squares
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这是一个求最优解的问题，需要在候选数为完全平方数且其和为 $n$ 的限制条件下，使选中的元素个数最少。

暴力破解

如何枚举出所有情况？先找到可能的最大完全平方数 $m={\lfloor \sqrt n\rfloor}^2$ ，然后给定一个候选数序列 $[1,4,…,m]$ ，化成一个“人民币面值”问题。列举出所有组合，判断是否满足限制条件，再取最小元素个数的组合。

贪心算法

如何使得元素个数最少？当然是每一步都取可能的最大值。与辗转相除法类似，先减去对可能的最大完全平方数，再对剩下的部分进行相同操作。

然而！！！贪心算法在此例中得到的确实不是最优解。考虑输入为12。

动态规划

对于输入 $n$ ，候选序列 $[1,4,…,m]$ ，对做一次选择，譬如选中 $i$ ，那么剩余需要凑的值为 $n-i$ ，如果我们记 $dp[n]$ 为输入为 $n$ 的最少完全平方数的个数，那么有

$dp[n]=dp[n-i]+1$
而我们要做的就是选出这些选择里使得

$dp[n]$ 最小的选择。

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