[アルゴリズム/標準]1699:平方和(python)

自分より小さい平方数で問題を解く.
1から自乗数を減算し,対応するdp上に+1する.
min(dp[i],dp[i-平方数]+1)

N = int(input())
dp = [i for i in range(N + 1)]

for i in range(1, N + 1):
    for j in range(1, int(i ** 0.5) + 1):
        if dp[i] > dp[i - j * j] + 1:
            dp[i] = dp[i - j * j] + 1
print(dp[N])