题解 | #最少的完全平方数#

当做一般动态规划来做。

tar = int(input())

# dp[i] 是和为i+1所需的完全平方数的最小数量
dp = [float('inf') for _ in range(tar)]

# 初始化：记录完全平方数的位置
for i in range(int(tar**0.5)):
    dp[(1+i)**2-1] = 1
sqrs = []

# 动态规划迭代
for i in range(tar):
    if dp[i] == 1:  # i+1是完全平方数
        sqrs.append(i+1)
    else:
# choice是加上某个完全平方数之后等于i+1的所有数字，即i+1是在某个choice的基础上再加一个完全平方数
        choice = [i-sqr for sqr in sqrs]
        dp[i] = 1+min([dp[idx] for idx in choice])

print(dp[-1])