leetcode279.完全平方数
给你一个整数 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
思路： 跟leetcode322.零钱兑换-CSDN博客几乎一毛一样，只不过这里物品重量要自己计算
public int numSquares(int n) {
int [] dp=new int[n+1];
Arrays.fill(dp,-1);
dp[0]=0;
for(int i=1;i<=Math.sqrt(n);i++){
int temp=i*i;
for(int j=temp;j<n+1;j++){
if(dp[j]==-1&&dp[j-temp]!=-1)
dp[j]=dp[j-temp]+1;
else if(dp[j-temp]!=-1)
dp[j]=Math.min(dp[j],dp[j-temp]+1);
}
}
return dp[dp.length-1];
}