心路历程:
动态规划问题,建模为:
状态:当前要处理的整数
动作:选哪一个满足要求的完全平方数
返回值:和为当前整数的最少完全平方数
注意的点:
1、边界条件中需要去除x<0的时候的情况,可以用正无穷配合返回值的min去除
2、注意候选动作应该从1开始,而不是0
解法:动态规划
class Solution:
def numSquares(self, n: int) -> int:
@cache
def dp(x): # 和为x的完全平方数的最少个数
if x < 0:
return float('inf')
if x == 0:
return 0
# 获取候选动作集合
candicate = []
for i in range(1, x+1):
if i * i <= x: candicate.append(i * i)
else: break
res = []
for action in candicate:
res.append(1 + dp(x - action))
return min(res)
return dp(n)