279.完全平方数
题目
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
给你一个整数 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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/perfect-squares
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
## 题解
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。
---> 从一个数组(一堆数)中按一定的选取方式得到目标target，尝试将题目进行转化为背包问题。
背包的容量是n，物品是从 1*1、2*2、3*3...、m*m中选择，其中m*m<=，每个物品可以多次选择，那么这是一道完全背包问题。
**1.确定dp[j]及下标的含义**
dp[j]:表示组成j的完全平方数个数最少为dp[j]。
**2.递推公式**
dp[j]可以由两种方式推出。
假设当前物品是num
- 组成j-num的完全平方数个数最少为dp[j-num],那么此时num放入之后，组成j的完全平方数个数为dp[j-num]+1。
- 当前num不放入，之前的物品已经组成了j的背包，个数为dp[j]
题目要求求最少的个数，那么递推式为`dp[j]=Math.min(dp[j],dp[j-num]+1)`
**3.dp数组如何初始化**
n=0，dp[0]=0
n≠0，涉及到求最小值，那么初始化应该为Integer.MAX_VALUE
**4.确定遍历顺序**
这是求最少的个数，不涉及什么组合排序，所以都可以。
先从小到大遍历物品，再从小到大遍历背包。
```java
for(int i=1;i*i<=n;i++){
int num = i*i;
for(int j=num;j<=n;j++){
//if(dp[j-num]!=Integer.MAX_VALUE) 这个注释掉是因为总会由办法凑齐1+1+1+...
dp[j]=Math.min(dp[j],dp[j-num]+1);
}
}
5.举例推导dp数组
n=4
代码
class Solution {
public int numSquares(int n) {
int [] dp = new int [n+1];
Arrays.fill(dp,Integer.MAX_VALUE);
dp[0] = 0;
for(int i=1;i*i<=n;i++){
int num=i*i;
for(int j=num;j<=n;j++){
dp[j]=Math.min(dp[j],dp[j-num]+1);
}
}
return dp[n];
}
}