279. 完全平方数

Difficulty
Medium
Tags
动态规划
URL
https://leetcode.cn/problems/perfect-squares/
Star
给你一个整数 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 <= 104
通过次数285,246提交次数439,573

法 1 动态规划 -完全背包

思路
完全背包，只不过本题的物品需要自己构造
题解
class Solution:
    def numSquares(self, n: int) -> int:
        # 先 构造一个背包出来
        i = 1
        nums = [0]
        while i * i <= n:
            nums.append(i*i)
            i += 1

        dp = [[float("inf")] * (n+1) for _ in range(len(nums)+1)]
        dp[0][0] = 0
    
        res = n
        for i in range(1, len(nums)+1):
            dp[i][0] = 0
            for j in range(1, n+1):
                dp[i][j] = dp[i-1][j]
                if j - nums[i-1] >= 0:
                    dp[i][j] = min(dp[i][j], dp[i][j-nums[i-1]]+1)


            res = min(res, dp[i][n])
        
        return res

法 2 BFS

思路
像下图一样裂变下去，直到遇到一个叶子节点为 0 的，本质上是在计算层数。
										n
						n-1   n-4   n-9,...
				n-1-1 n-1-4
题解
class Solution:
    def numSquares(self, n: int) -> int:
        if n == 0:
            return 0

        queue = deque()
        queue.append(n)
        visited = set()
        visited.add(n)
        step = 0
        while queue:
            size = len(queue)
            step += 1
            while size > 0:
                num = queue.popleft()
                size -= 1
                
								# 邻居节点
                temp = 1
                while temp * temp <= num: 
                    target = num - temp * temp
                    if target == 0:
                        return step
                    if target not in visited:
                        queue.append(target)
                        visited.add(target)
                    temp += 1