279. 完全平方数
-
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
-
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
1. 动态规划
- 思路:
-
初始化：dp[0] = 0，因为和为 0 不需要任何完全平方数
-
对于每个i (1~n)，遍历所有小于等于 i 的完全平方数 j * j，并更新 dp[i] 为 dp[i - j * j] + 1 的最小值
-
class Solution(object):def numSquares(self, n):""":type n: int:rtype: int"""# 初始化dp数组, dp[i]表示和为i的完全平方数的最少数量dp = [float('inf')] * (n + 1)dp[0] = 0 # 和为0不需要任何完全平方数for i in range(1, n + 1):# 遍历所有小于等于i的完全平方数for j in range(1, int(math.sqrt(i)) + 1):dp[i] = min(dp[i], dp[i - j*j] + 1)return dp[n]
-
时间复杂度：O(n * sqrt(n))，因为需要遍历1到 n，并且对于每个 i，最多需要遍历 sqrt(i) 次
-
空间复杂度：O(n)，使用了一个大小为 n+1 的数组 dp
2. 广度优先搜索
-
思路:
-
将 n 作为起始节点
-
每次从当前节点减去一个完全平方数，得到新的节点
-
使用 BFS 来找到从 n 到 0 的最短路径
-
class Solution(object):def numSquares(self, n):""":type n: int:rtype: int"""# 生成所有小于等于n的完全平方数squares = [i * i for i in range(1, int(n**0.5) + 1)]# BFS 队列，存储 (当前值, 步数)queue = deque([(n, 0)])visited = set() # 记录已经访问过的节点while queue:current, steps = queue.popleft()# 遍历所有完全平方数for square in squares:next_val = current - squareif next_val == 0: # 找到目标return steps + 1if next_val > 0 and next_val not in visited:visited.add(next_val)queue.append((next_val, steps + 1))return -1 # 如果没有找到，返回 -1（理论上不会发生）
-
时间复杂度：O(n * sqrt(n))，BFS 最多会遍历 n 个节点，每个节点最多有 sqrt(n) 条边
-
空间复杂度：O(n)，用于存储队列和访问记录
