大家好！我是曾续缘😜
今天是《LeetCode 热题 100》系列
发车第 84 天
动态规划第 4 题
❤️点赞 👍 收藏 ⭐再看，养成习惯

给你一个整数 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 <= 10⁴
难度：💖💖

解题方法

定义一个数组 f，其中 f[i] 表示和为 i 的完全平方数的最少数量。

初始化数组 f，将每个位置的初始值设为一个较大的数，这里取 10004（大于 10^4，题目所给范围）。

接着，我们从 2 开始遍历到 n，对于每个数 i，我们尝试用完全平方数来表示它。

内层循环中，我们遍历所有小于等于 i 的平方数，假设为 j*j，然后更新 f[i] 为 f[i-j*j] + 1 和当前 f[i] 的较小值。

最终返回 f[n] 即可得到和为 n 的完全平方数的最少数量。

Code

查看代码

java

public class Solution {
    public int numSquares(int n) {
        // 初始化数组 f，用于存储和为 i 的完全平方数的最少数量
        int[] f = new int[n+1];
        Arrays.fill(f, 10004); // 初始化为一个较大的数
        f[0] = 0; // 和为 0 的完全平方数数量为 0
        f[1] = 1; // 和为 1 的完全平方数数量为 1
        
        // 从 2 开始遍历到 n
        for (int i = 2; i <= n; i++) {
            // 遍历所有小于等于 i 的平方数
            for (int j = 1; j*j <= i; j++) {
                // 更新 f[i] 为 f[i-j*j] + 1 和当前 f[i] 的较小值
                f[i] = Math.min(f[i], f[i-j*j] + 1);
            }
        }
        
        return f[n]; // 返回和为 n 的完全平方数的最少数量
    }
}

解题方法 ​

Code ​

解题方法

Code