LeetCode-279 完全平方数

题目来源

LeetCode-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

题解分析

完全背包问题变形-二维数组解法

1. 从题目可以分析出，这题其实是完全背包问题的变形，整个题目都能看到完全背包问题的影子。
2. 题目中的n就可以类比于背包的容量，这些计算出来的完全平方数就相当于商品，可以假设每个完全平方数的价值为1（相当于把个数看成价值）。
3. 由此，可以构造出状态转移数组，假设\(dp[i][j]\)表示前i个数中，可以拼凑出数字和恰好是j的最小数字个数。进而，根据定义，可以定义状态转移函数：\(dp[i][j] = Math.min(dp[i-1][j], dp[i][j-nums[i]] + 1)\)。
4. 需要注意的是，这里的状态转移方程中的第二个条件，dp[i][j-1]是与01背包不同的地方，因为这些平方数可以选择无限个，其实\(dp[i][j-nums[i]] + 1\)是应该写成\(dp[i-1][j-k*nums[i]] + k\)（k表示平方数使用的个数）的形式的。但是我们仔细观察迭代式可以知道：其实\(dp[i][j-nums[i]] + 1\)已经计算过了这个式子：\(dp[i-1][j-k*nums[i]] + k\)。所以在状态转移方程里，我们可以直接写成复用前一个式子的形式。
5. 最后，我们还得考虑一下边界值。\(dp[i][0]\)可以表示为前i个数中选出若干个数的和为0的最小个数，这其实可以赋值为0，因为不可能拼凑出0，因为最小的平方数都是1。而\(dp[0][j]\)则可以理解为用0个数拼凑出j是绝不可能的，所以赋值为最大值0X3F3F3F3F。

class Solution {
    final int MAXS = 0X3F3F3F3F;
    public int numSquares(int n) {
        int sn = (int)Math.sqrt(n);
        int[] nums = new int[sn+1];
        for(int i=0; i<=sn; i++){
            nums[i] =  i * i;
        }
        // dp[i][j] = min(dp[i-1][j], dp[i][j-nums[i]])
        int[][] dp = new int[sn+1][n+1];
        for(int i =0; i<=sn; i++){
            Arrays.fill(dp[i], MAXS);
            dp[i][0] = 0;
        }
        
        for(int i=1; i<=sn; i++){
            for(int j=1; j<=n; j++){
                if(j >= nums[i]){
                    dp[i][j] = Math.min(dp[i-1][j], dp[i][j-nums[i]] + 1);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[sn][n];
    }
}

完全背包优化-一维数组解法

1. 学过背包问题的可能都有所了解，背包问题一般都可以进行数组维度的优化。
2. 从我们的状态转移方程（\(dp[i][j] = Math.min(dp[i-1][j], dp[i][j-nums[i]] + 1)\)）也可以看到，当前状态只依赖于上一层的状态以及本轮之前已经计算过的状态。所以，可以将dp退化为一维数组，然后采用正序遍历j的方法，这么做的原因是需要取到本轮迭代中前面计算的值\(dp[i][j-nums[i]]\)。
3. 最后，也要考虑一下边界值的计算，这里只有\(dp[0]\)可以被赋值为0，其他位置（类似于解法一中的\(dp[0][j]\)）都被赋值为无穷大：0X3F3F3F3F。
4. 代码如下：

class Solution {
    final int MAXS = 0X3F3F3F3F;
    public int numSquares(int n) {
        int sn = (int)Math.sqrt(n);
        int[] nums = new int[sn+1];
        for(int i=0; i<=sn; i++){
            nums[i] =  i * i;
        }
        // dp[i][j] = min(dp[i-1][j], dp[i][j-nums[i]])
        int[] dp = new int[n+1];
        Arrays.fill(dp, MAXS);
        dp[0] = 0;
        
        for(int i=1; i<=sn; i++){
            for(int j=nums[i]; j<=n; j++){
                dp[j] = Math.min(dp[j], dp[j-nums[i]] + 1);
            }
        }
        return dp[n];
    }
}