[アルゴリズム/標準]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])Reference
この問題について([アルゴリズム/標準]1699:平方和(python)), 我々は、より多くの情報をここで見つけました https://velog.io/@y7y1h13/알고리즘백준-1699-제곱수의-합pythonテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol