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

# 16:58

import sys
import math
# dp[i]: 数为i时的最小个数完全平方数
# dp[i] = 1 if i等于某个平方数， else dp[i] = min(dp[i-k] + 1, k 为某个平方数，dp[i]的最小值肯定是dp[i-某个平方数]+1，因此可以把k限制在平方数的个数上

# 为了加速，

n = int(input())
candidates = []
m = 1
max_num = 10**4
dp = [max_num+1] * (n+1)
while m*m <= n:
    candidates.append(m*m)
    dp[m*m] = 1
    m+=1

for i in range(1,n+1):
    for k in candidates:
        dp[i] = min(dp[i],dp[i-k] + 1)
print(dp[-1])