LeetCode-热题100：279. 完全平方数

题目描述

给你一个整数 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⁴

代码及注释

func numSquares(n int) int {
    // 初始化一个长度为 n+1 的数组 res，用于存储每个数字 i 对应的最少完全平方数的数量
    res := make([]int, n + 1)
    
    // 遍历从 1 到 n 的每个数字
    for i := 1; i <= n; i++ {
        // 初始化一个非常大的数作为最小数量
        minNum := math.MaxInt32
        
        // 对于每个数字 i，尝试所有可能的完全平方数 j*j
        for j := 1; j * j <= i; j++ {
            // 更新最小数量
            minNum = min(minNum, res[i - j * j])
        }
        
        // 当前数字 i 的最少完全平方数数量是 minNum 加上 1
        res[i] = minNum + 1
    } 
    
    // 返回 n 对应的最少完全平方数数量
    return res[n]
}

// 辅助函数，返回两个数的最小值
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

代码解释

这里使用了动态规划的方法：

• 定义 res[i] 为和为 i 的完全平方数的最少数量。
• 对于每个数字 i，我们遍历所有可能的完全平方数 j*j，并更新最小数量。
• 最后，res[n] 就是和为 n 的完全平方数的最少数量。

例如，对于 n = 12，解释如下：

• 对于 i = 1，res[1] = res[1-1*1] + 1 = res[0] + 1 = 1
• 对于 i = 2，res[2] = res[2-1*1] + 1 = res[1] + 1 = 2
• 对于 i = 3，res[3] = res[3-1*1] + 1 = res[2] + 1 = 3
• 对于 i = 4，res[4] = min(res[4-1*1], res[4-2*2]) + 1 = min(res[3], res[0]) + 1 = 1
• 对于 i = 5，res[5] = min(res[5-1*1], res[5-2*2]) + 1 = min(res[4], res[1]) + 1 = 2
• 对于 i = 6，res[6] = min(res[6-1*1], res[6-2*2]) + 1 = min(res[5], res[2]) + 1 = 3
• 对于 i = 7，res[7] = min(res[7-1*1], res[7-2*2]) + 1 = min(res[6], res[3]) + 1 = 4
• 对于 i = 8，res[8] = min(res[8-1*1], res[8-2*2]) + 1 = min(res[7], res[4]) + 1 = 2
• 对于 i = 9，res[9] = res[9-3*3] + 1 = res[0] + 1 = 1
• 对于 i = 10，res[10] = min(res[10-1*1], res[10-2*2], res[10-3*3]) + 1 = min(res[9], res[6], res[7]) + 1 = 2
• 对于 i = 11，res[11] = min(res[11-1*1], res[11-2*2], res[11-3*3]) + 1 = min(res[10], res[7], res[8]) + 1 = 3
• 对于 i = 12，res[12] = min(res[12-1*1], res[12-2*2], res[12-3*3], res[12-4*4]) + 1 = min(res[11], res[8], res[9], res[0]) + 1 = 3

因此，n = 12 时，和为 12 的完全平方数的最少数量是 3。