279. 完全平方数

题目链接
代码随想录

分析

这一题跟 322. 零钱兑换 如出一辙，区别就是我们需要自己确定物品数组，其实很简单，就是把以 1 到 n 为基础的所有快乐数找出来即可，为什么？
因为一个多个完全平方数的和为 n，那么组成和的最大的完全平方数 x，应该有 $x^2<=n$，因此 $x<=\sqrt[2]{n}$ ，因此 有 $x<=n$。所以我们只要把从 1 到 n 的这些数的平方作为物品，放到容量为 n 的包里，而且每一个物品都可以重复放入，求当我们刚好把背包放满的时候，物品数量最少是多少，这个题跟 322. 零钱兑换 真的一模一样。
我们按照动态规划五部曲来解题
定义 dp 数组：dp[j] 为和为 j 的时候组成 j 的完全平方数的最小个数。
状态转移方程：dp[j] = Math.min(dp[j],1+dp[j-nums[i]]);，因为我们求的是背包被塞满的情况下的最小物品个数。因此使用这个状态转移方程需要同时满足两个条件，

• 使用物品 i 的时候，dp[j-nums[i]] 得有值（存在能塞满容量为 j-nums[i] 的背包的完全平方数的组合）
• 不使用物品 i 的时候，dp[j] 得有值（存在能塞满容量为 j 的背包的完全平方数的组合）
  因此我们需要判断，
• 如果 dp[j-nums[i]] 有值
  • 如果 dp[j] 有值，使用状态转移方程：dp[j] = Math.min(dp[j],1+dp[j-nums[i]]);
  • 如果 dp[j] 没值，直接 dp[j] = 1+dp[j-nums[i]];
• 如果 dp[j-nums[i]] 没有值，直接放弃更新 dp[j]
  初始化的情况。
  因为 dp[j] 存在两种情况，
• 不存在多个物品可能凑满背包的组合
• 存在多个物品可能凑满背包的组合，而且组合的最小个数为 dp[j]
  因此为了区分这两种情况，我们把 dp 数组的所有元素初始化为 -1，同时 dp[0]=0; 因为塞满容量为 0 的背包的物品数量为 0.
  然后是遍历顺序，因为求的是最小组合数，所以可以不在乎内外层 for 哪个在外面哪个在里面，于是我们选择更好理解的，外层 for 循环遍历物品，内层 for 循环遍历容量，而且因为是完全背包，所以从 nums[i] 遍历导容量最大值。如果是 01 背包，就得从容量最大值遍历到 coin[i] 了。
  为什么可以不在乎内外层 for 哪个在外面哪个在里面？请看 377. 组合总和 Ⅳ#什么时候可以不在乎内外层 for 循环哪个在外面哪个在里面

小优化。
其实在使用状态转移公式之前，也可以不判断 dp[j-nums[i]]、dp[j] 是否有值，因为 n 一定可以拆成多个 1 的和，而 1 是完全平方数，所以 dp[j-nums[i]] 至少都是有一个值，就是 j-nums[i]，不会是 -1。把 dp 数组输出就可以确认这一点了。
例如 n=12，输出的 dp 数组为

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
[0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3]
[0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3]
[0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3]
[0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3]
[0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3]
[0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3]
[0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3]
[0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3]
[0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3]
[0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3]
[0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3]

确实没有 -1。
因此可以简化。

解题

public int numSquares(int n) {
    int[] nums = new int[n];
    for(int i=1;i<=n;i++){
        nums[i-1]=i*i;
    }
    int[] dp = new int[n+1];
    for(int i=0;i<n+1;i++){
        dp[i]=-1;
    }
    dp[0]=0;
    for(int i=0;i<nums.length;i++){
        for(int j=nums[i];j<n+1;j++){
            if(dp[j-nums[i]]!=-1){
                if(dp[j]!=-1){
                    dp[j] = Math.min(dp[j], 1+ dp[j-nums[i]]);        
                }else{
                    dp[j] = 1+ dp[j-nums[i]];        
                }
            }
        }
    }
    return dp[n];
}

简化

public int numSquares(int n) {
    int[] nums = new int[n];
    for(int i=1;i<=n;i++){
        nums[i-1]=i*i;
    }
    int[] dp = new int[n+1];
    for(int i=0;i<n+1;i++){
        dp[i]=Integer.MAX_VALUE;
    }
    dp[0]=0;
    for(int i=0;i<nums.length;i++){
        for(int j=nums[i];j<n+1;j++){
            dp[j] = Math.min(dp[j], 1+ dp[j-nums[i]]);        
        }
    }
    return dp[n];
}

相关题

322. 零钱兑换