【LeetCode】【算法】279. 完全平方数

LeetCode 279. 完全平方数

题目描述

给你一个整数 n ，返回和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4

示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9

思路

和LeetCode 322.零钱兑换很类似，这里也是使用动态规划的思路求解。

1. 创建dp动态数组，每个索引下标i表示组成值i最少需要几个完全平方数；
2. 数组初始化：dp[0]=0；对于其他每个下标i，组成值i最少需要i个1（1是完全平方数），所以初始化就是让dp[i]=i；
3. 嵌套循环填充dp数组，第一个for循环遍历从i~n，循环体内部求和为n的完全平方数的最少数量；
4. 第二个for循环遍历的终止条件是i-j*j>=0，jj实际上就是完全平方数，j的遍历范围从1开始，每次+1，那么jj的结果就是从1,4,9,16…依次在各个完全平方数内变换。这一点和零钱兑换的那题很类似，实际上就是遍历不超过i的完全平方数（因为完全平方数超过i必不可能组成i，和零钱兑换中的if条件是类似的，如果你的硬币币值>目标金额的话，这个硬币也不可能被用于组成目标金额）
5. 对于动态转移方程，求的是和为n的完全平方数的最少数量，故dp[i]=Math.min(dp[i],dp[i-j*j]+1)，前面也就是不使用完全平方数j时候的结果，后面是使用完全平方数j的结果
6. return dp[n];

代码

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1]; // dp数组中的每个下标i表示，组成值i完全平方数的最少数量
        // 填充dp数组
        for (int i = 1; i <= n; i++) {
            dp[i] = i; // 最坏的情况就是，该数由许多1组成，实际上这里设置成Integer.MAX_VALUE也可以
            for (int j = 1; i - j * j >= 0; j++){
                // 首先说明for循环的条件为什么是: i-j*j>=0，首先变换一下i>=j*j
                // j*j实际上就凑成了一个“完全平方数”，在这个for循环里，j的值从1开始，每次不断+1，那么j*j的值就是1,4,9,16...，每次都是完全平方数
                // 这里实际上就是“假设我们使用这个完全平方数”时
                // i-j*j中，我们想求i需要多少个完全平方数凑成
                // 也就是使用了这个完全平方数后的数（j*j是完全平方数，i-j*j是剩余的数值），剩余的数值最少需要由几个完全平方数凑成
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }
}