279. 完全平方数 · Algorithm Lab

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

参考解法

下面保留的是原始练习仓库中的个人作答，可在右侧工作台中独立重写，再按需揭示对照。

python


class Solution(object):
    def numSquares(self, n):
        dp = [n] * (n + 1)  # 初始化为一个较大值，如 inf 或 n
        dp[0] = 0

        # 完全背包
        i = 1
        while i * i <= n:  # 第一层循环：判断i*i
            num = i * i
            for j in range(num, n + 1):  # 第二层循环：遍历背包【正序】
                dp[j] = min(dp[j], dp[j - num] + 1)
            i += 1
        return dp[-1]
        """
        :type n: int
        :rtype: int
        """