279完全平方数

发表于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def numSquares(self, n: int) -> int:
        # 还是一个完全背包的问题，装满背包的最小物品数量。
        # d[j] 是 j容量 下 能装满的最小的数量。
        d = [10**4 for _ in range(n+1)]
        d[0] = 0
        for i in range(1,n+1):
            for j in range(i**2,n+1):
                d[j] = min(d[j-i**2]+1,d[j])
                # print(d)
        return d[-1]