leetcode刷题记录（一百零七）——279. 完全平方数
（一）问题描述
279. 完全平方数 - 力扣（LeetCode）279. 完全平方数 - 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。 示例 1：输入：n = 12输出：3 解释：12 = 4 + 4 + 4示例 2：输入：n = 13输出：2解释：13 = 4 + 9 提示： * 1 <= n <= 104
https://leetcode.cn/problems/perfect-squares/description/?envType=study-plan-v2&envId=top-100-liked
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n =12输出：3 解释：12 = 4 + 4 + 4示例 2：
输入：n =13输出：2 解释：13 = 4 + 9
提示：
1 <= n <= 10^4
（二）解决思路
这个问题属于完全背包问题：想象有一个背包，它的容量是j；有一堆物品，对于物品i，它的重量是weights[i]，价值是value[i]，那么当背包填满时，求它的价值最大是多少。 这道题的特殊指出在于它求的是最小值，思路其实是一样的，把取最大值改成取最小值就好了。
在这道题里可能出现的问题：是不是所有背包都可以被“填满“，即是否会出现某个数不能转换成一系列完全平方数的和。答案是否定的，因为1也是完全平方数，无论如何都能用1凑满。
创建dp数组，dp数组的下标j代表此时背包的容量为 j，dp[j]代表背包容量剩余j时所能存放的最大价值。在这道题中是当n中还剩下 j 这么大时，最少要用dp[j]个完全平方数填充剩下的部分j。将dp数组中每个元素的初始值设置为Integer.MAX_VALUE，即整数中的最大值，这样它不会在取最小值时被覆盖。不难想到 j 的最大值是n，且dp[0]=0；
遍历每一个物品，物品需要满足条件i*i<=n（否则由 i 形成的完全平方数就没有办法做n的组成部分啦，并且要注意这里是<=不是<）。对于每个物品，当背包剩余容量为 j 时，思考要不要放它。如果不放，完全平方数个数将是d[j]，即保持不变；如果放，那么完全平方数的个数就是上一次放东西时的剩余大小，即dp[j-i*i]，再加上这一次添加的一个物品，总物品个数就是dp[j-i*i]+1。比较放和不放的结果，去效果更好，即总个数最少的一个：Math.min(d[j],dp[j-i*i])。
class Solution {
public int numSquares(int n) {
//完全背包问题
//完全平方数就是物品，n是背包
int[] dp = new int[n+1];
Arrays.fill(dp,Integer.MAX_VALUE);
dp[0]=0;
for(int i=1;i*i<=n;i++){
for(int j=i*i;j<=n;j++){
dp[j]=Math.min(dp[j],dp[j-i*i]+1);
}
}
return dp[n];
}
}