LeetCode 279. 完全平方数

题目

给你一个整数 n ，返回和为 n 的完全平方数的最少数量。完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

例：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4

方法：动态规划

本题为完全背包，因为完全平方数是无限的。思路类似 322. 零钱兑换

• dp[j] 表示和为 j 的完全平方数的最少数量，初始化为正无穷，因为求的是最少数量，若非大于和 n 的值，则可能导致该值被覆盖
• 当整数为零时，完全平方数的最少数量为零，即 dp[0] = 0
• nums 表示小于等于 n 的所有完全平方数的列表
• 外部循环为对完全平方数（物品）的正序循环，内部循环为对和 n 的正序循环
• 递推公式：该次 dp[j] 的最少数量表示为，原 dp[j] 的值和新值（即在加入完全平方数 num 后和达到 j）进行比较后较小的那个

class Solution(object):
    def numSquares(self, n):
        dp = [float('INF')] * (n + 1)
        dp[0] = 0
        nums = []
        for i in range(1, n+1):
            if i**2 <= n:
                nums.append(i**2)
        for num in nums:
            for j in range(num, n + 1):
                dp[j] = min(dp[j], dp[j-num] + 1)
        return dp[n]

参考

代码相关：https://programmercarl.com/0279.%E5%AE%8C%E5%85%A8%E5%B9%B3%E6%96%B9%E6%95%B0.html