一、问题描述

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

二、方案一：广度优先搜索（BFS）

1、思路

我们可以将这个问题看作是一个图的问题，其中节点表示数字，边表示从一个数字到另一个数字的减法操作。我们想要找到从 n 到 0 的最短路径，其中路径上的每个节点都是某个数的完全平方。 我们可以使用广度优先搜索（BFS）来解决这个问题。从 n 开始，对于每个数字，我们尝试减去所有可能完全平方数，并将结果添加到队列中。我们使用一个集合来记录访问过的数字，以避免重复访问。

2、代码实现

func numSquares(n int) int {
    // 初始化队列和集合
    queue := []int{n}
    visited := make(map[int]bool)
    visited[n] = true
    // 广度优先搜索
    level := 0
    for len(queue) > 0 {
        level++
        size := len(queue)
        for i := 0; i < size; i++ {
            num := queue[0]
            queue = queue[1:]
            // 尝试减去所有可能的完全平方数
            for j := 1; num-j*j >= 0; j++ {
                next := num - j*j
                if next == 0 {
                    return level // 找到最短路径
                }
                if !visited[next] {
                    visited[next] = true
                    queue = append(queue, next)
                }
            }
        }
    }
    return level
}

3、复杂度分析

• 时间复杂度：O(n^1.5)，因为对于每个数字，我们可能需要尝试减去最多 sqrt(n) 个完全平方数。
• 空间复杂度：O(n)，因为我们需要存储队列和集合。

三、方案二：动态规划

1、思路

动态规划方法是基于这样一个事实：如果我们知道组成数字 x 的完全平方数的最小数量，那么我们可以通过尝试减去每个完全平方数来计算组成数字 x + k^2 的完全平方数的最小数量。 我们可以使用一个数组 dp，其中 dp[i] 表示组成数字 i 的完全平方数的最小数量。我们初始化 dp[0] = 0，然后对于每个数字 i，我们尝试减去每个完全平方数 j^2，并更新 dp[i]。

2、代码实现

func numSquares(n int) int {
    // 初始化动态规划数组
    dp := make([]int, n+1)
    for i := 1; i <= n; i++ {
        dp[i] = math.MaxInt32
    }
    // 动态规划
    for i := 1; i <= n; i++ {
        for j := 1; j*j <= i; j++ {
            dp[i] = min(dp[i], dp[i-j*j]+1)
        }
    }
    return dp[n]
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

3、复杂度分析

• 时间复杂度：O(n*sqrt(n))，因为我们需要计算每个数字的 dp 值，对于每个数字，我们可能需要尝试减去最多 sqrt(n) 个完全平方数。
• 空间复杂度：O(n)，因为我们需要存储动态规划数组。

四、总结

方案	时间复杂度	空间复杂度	备注
BFS	O(n^1.5)	O(n)	适用于 n 不是特别大的情况
动态规划	O(n*sqrt(n))	O(n)	适用于 n 较大的情况
根据 n 的大小，我们可以选择合适的方案来解决这个问题。