2️⃣279.完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

思路

基本思想

每个数都可以表示成完全平方数的和，并且至少有一种可能，例如3可以表示成3=1+1+1，而1就是完全平方数，本题的目的是求出最少的完全平方数

当前物品可以看做是数，并且数可以重复，也就是完全背包问题，确定递推公式最困难，当前数放进背包，也就代表着当前数要被拆分，被放进背包的数不好判断是不是完全平方数，可以直接让其成为完全平方数，也就是放进背包的数为i*i，此时一定是完全平方数，由此确定递推公式为： $$ dp[j]=min(dp[j],dp[j-i*i]+1) $$ i*i放进去之后，正整数多一个，其中dp[j]代表和为j的完全平方数的最少数量

根据以上分析，i*i不能超过n

执行流程

1. 初始化dp数组为当前范围的无穷大，便于更新到最小值
2. dp[0]=0
3. 按照完全背包的流程更新dp数组
4. 返回dp[n]作为最终的结果

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1,INT_MAX);
        dp[0]=0;
        for(int i=0;i*i<=n;++i){//i*i超过n没有意义
            for(int j=i*i;j<=n;++j){//完全背包从前向后
                if(dp[j-i*i]!=INT_MAX){//防止+1之后超过int的范围
                    dp[j]=min(dp[j],dp[j-i*i]+1);
                }
            }
        }
        return dp[n];
    }
};

总结

主要是转换思维，当前数不要直接放入，而是将其平方之后放入，这样就可以得到转移方程： $$ dp[j]=min(dp[j],dp[j-i*i]+1) $$ i*i放进去之后，还剩下j-i*i，此时正整数的个数加一，然后取最小的方案数

只要转换了思维，放进去的是i*i，而不是i再去判断是不是完全平方问题迎刃而解，因为这样每次放进去的都是完全平方数