力扣279-完全平方数（Java详细题解）

题目链接：279. 完全平方数 - 力扣（LeetCode）

前情提要：

因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。

最近刚学完背包，所以现在的题解都是以背包问题为基础再来写的。

如果大家不懂背包问题的话，建议可以去学一学01背包和完全背包。

如果大家感兴趣，我后期可以出一篇专门讲解背包问题。

dp五部曲。

1.确定dp数组和i下标的含义。

2.确定递推公式。

3.dp初始化。

4.确定dp的遍历顺序。

5.如果没有ac打印dp数组利于debug。

每一个dp题目如果都用这五步分析清楚，那么这道题就能解出来了。

这里下文统一使用一维dp数组。

题目思路:

该题很好入手，求凑成和为n所用的完全平方数的最小数量。完全平方数可以取无数次。

由此可见这是一个完全背包问题。

n可以抽象为背包容量，所用的完全平方数可以抽象为物品。

本题可以转化为将这个背包装满所用物品的最少数量。

这样一看这个题就跟力扣322-零钱兑换很像，都是求背包装满所用物品的最少数量。唯一不同的就是物品不一样，零钱兑换是把物品数量什么的都给出来了，该题的物品没给出来，需要我们自己创建。

接下来我们用动规五部曲系统分析一下。

1.确定dp数组和i下标的含义。

dp[j] 指的就是凑成和为j时，所用物品的最少数量。

2.确定递推公式。

本题是要求能装物品的最少数量。

本题的物品为完全平方数，也就是i的平方。

我们可以遍历i然后让他的平方作为物品。

每个物品只有俩个状态，选和不选。

当这个物品不选时，dp数组就为dp[j]。因为它不选，所以背包容量不会减少,物品数量也不会变，所以就为dp[j]

当这个物品选的时候，dp数组为dp[j - i * i + 1]。因为选择了i * i作为物品，所以我们要知道选择i * i之前的背包容量所能装的最少物品数量，然后选择了这个物品，那我们的物品数量就会加1。

因为我们是要求装满后最少的物品数量，所以需要将这个物品选和不选的情况取一个最小值。

所以我们的递推公式就为：dp[j] = Math.min(dp[j],dp[j - i * i] + 1]);

3.dp初始化。

本题的初始化有很大讲究。

dp[0] 是指当背包容量为0时，能凑成0的最少硬币个数。硬币最小就为1。所以dp[0] = 0;

之前我们求的都是最大值，所以将非0下标初始化为0，是为了防止初始化的值来覆盖递推出来的值。

本题是求最小值，如果我将非0下标也初始化为0，那么我初始化的0就会将我递推出来的最小值覆盖，最后得出来为0。

因为我递推的最小值不可能比0更小。

所以在这里我们要将非0下标初始化为一个不影响我递推公式的值（不可能被dp数组取到的值），这个值可以为Integer.MAX_VALUE。

因为我初始化为最大的数值，其他的数肯定小于等于它，当我递推出一个比它小的值时，就能覆盖这个最大值，不影响我递推的值。

说简单点。

要求最大值的时候，尽量初始化为更小的数。

要求最小值的时候，尽量初始化为更大的数。

4.确定dp的遍历顺序。

在完全背包问题中，如果先遍历物品再遍历背包就是求的物品的组合。

如果先遍历背包后遍历物品就是求的物品的排列。

该题是求凑成和为n的最少平方数个数。

举个例子。如果我的总和为6，平方为1和4。

那我凑成这个金额的硬币可以是{1,1,4}也可以是{4,1,1}。

这俩种情况最少平方数个数都为3。所以我物品的排列组合是不影响我dp数组的。

所以该题既可以先遍历物品也可以先遍历背包。

5.如果没有ac打印dp数组利于debug。

在这里插入图片描述

最终代码：

java">class Solution {
    public int numSquares(int n) {
        //该题也是求将背包装满的最少物品数量
        //定义dp数组
        int [] dp = new int [n + 1];
        //dp数组初始化
        //注意这里从1开始 dp[0] 默认初始化为 0
        for(int i = 1;i <= n;i ++){
            dp[i] = Integer.MAX_VALUE;
        }
        //先遍历物品后遍历背包
        //为什么这里i * i <= n呢？ 这是指当前物品（平方和）小于 背包容量，如果我当前的物品大于背包容量，我就没必要装了。
        for(int i = 1;i * i <= n;i ++){
            j 初始化为 i * i 是为了避免数组dp[j - i * i]越界 
            //代码层次上讲是避免越界 思路上讲就是你在选择该物品前，得先确定你的背包容量能够装下该物品
            for(int j = i * i;j <= n;j ++){
                dp[j] = Math.min(dp[j],dp[j - (i * i)] + 1);
            }
        }
        return dp[n];
    }
}