My Seventy-ninth Page - 完全平方数 - By Nicolas

这篇page是针对leetcode上的279.完全平方数所写的。小尼先简单的说明一下这道题的意思，就是给出一个整数n，返回和为n的完全平方数的最小数量。

其实这道题就是一个典型的完全背包问题，我们可以把给出的整数n看作是背包容量的大小，给出的所有的完全平方数就是我们背包中需要放入的元素，我们在这里需要控制的一点就是我们如何将我们给入dp数组的范围控制好，其实也就是如何将我们的递归的条件控制好。

小尼接下来还是给出递归五部曲：

1、确定dp数组以及下标的含义：dp[j]是和为j的完全平方数的最少数量

2、确定递推公式：dp[j] = min(dp[j - i*i] + 1, dp[j])

3、dp数组如何初始化:dp[0]表示和为0的完全平方数的最小数量，那么dp[0]一定是0

4、确定遍历顺序：我们知道这是个完全背包，但是这道题我们需要求的只是一个数量，所以遍历的顺序也就是我们外层如何遍历以及内层如何遍历都是可以的，小尼等会给出两种遍历的写法

5、再就是导出dp数组

接下来，小尼将给出这道题的解体的代码:

class Solution {
    // 版本一，先遍历物品, 再遍历背包
    public int numSquares(int n) {
        int max = Integer.MAX_VALUE;
        int[] dp = new int[n + 1];
        //初始化
        for (int j = 0; j <= n; j++) {
            dp[j] = max;
        }
        //当和为0时，组合的个数为0
        dp[0] = 0;
        // 遍历物品
        for (int i = 1; i * i <= n; i++) {
            // 遍历背包
            for (int j = i * i; j <= n; j++) {
                if (dp[j - i * i] != max) {
                    dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
                }
            }
        }
        return dp[n];
    }
}

class Solution {
    // 版本二， 先遍历背包, 再遍历物品
    public int numSquares(int n) {
        int max = Integer.MAX_VALUE;
        int[] dp = new int[n + 1];
        // 初始化
        for (int j = 0; j <= n; j++) {
            dp[j] = max;
        }
        // 当和为0时，组合的个数为0
        dp[0] = 0;
        // 遍历背包
        for (int j = 1; j <= n; j++) {
            // 遍历物品
            for (int i = 1; i * i <= j; i++) {
                dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
            }
        }
        return dp[n];
    }
}

上面就是两种循环交替解决的方法。

希望上面的分析和代码可以帮助到小伙伴们~~~