题目：279. 完全平方数
我的感悟：
- 看文字也行
理解难点：
- 物品是什么？是i*i<n的集合
听课笔记：
代码示例：
class Solution:
def numSquares(self, n: int) -> int:
# 完全背包问题
# 顺序没关系,组合把
# 递推公式难想,dp[j] = min(dp[j],dp[j-i*i]+1)
# 物品是什么? 有限值 i*i <n
# 背包n
# dp[j] 含义是到整数j，包含完全平方的最小数量
dp = [float('inf')] * (n+1)
dp[0] = 0
for i in range(1,int(n**0.5)+1): # 遍历物品
for j in range(n+1): # 这里前边界写不对也没关系 # 写成这样是最对的 range(i * i, n + 1)
if j-i*i >=0: # 补充
dp[j] = min(dp[j],dp[j-i*i]+1)
# print(dp)
return dp[n]通过截图：
边界写对的写法：
class Solution:
def numSquares(self, n: int) -> int:
dp = [float('inf')] * (n + 1)
dp[0] = 0
for i in range(1, int(n ** 0.5) + 1): # 遍历物品
for j in range(i * i, n + 1): # 遍历背包
# 更新凑成数字 j 所需的最少完全平方数数量 # 减少了判断
dp[j] = min(dp[j - i * i] + 1, dp[j])
return dp[n]资料：
279.完全平方数
本题 和 322. 零钱兑换 基本是一样的，大家先自己尝试做一做
视频讲解：https://www.bilibili.com/video/BV12P411T7Br
https://programmercarl.com/0279.%E5%AE%8C%E5%85%A8%E5%B9%B3%E6%96%B9%E6%95%B0.html
标签：平方,min,int,随想录,E5%,part7,day50,279,dp From： https://www.cnblogs.com/liqi175/p/18043321