📚 1699-平方和

平方和
 
問題を理解する

この問題では、nより小さい二乗の最値に基づいてソースを作成しようとしたが、

12の場合、9と3:4、8、4:3です.
➡️ dp[12] = 3

ビットの例に示すように、反例がある.

文を

2nに繰り返し、1 ~ nの間の平方数を検索してチェックします.△ソースコードからすれば、分かりやすいはずです.

 
私のソース

n = int(input())

dp = []

for idx in range(n + 1):
    dp.append(idx)

for i in range(2, n+ 1):
    for j in range(2, i+1):
        if j * j > i:
            break
        else:
            dp[i] = min(dp[i], dp[i - j * j] + 1)

print(dp[n])

 
リファレンスソース

# 참고하여 수정한 코드

n = int(input())

dp = [0] * (n + 1)

for i in range(1, n+ 1):
    dp[i] = i
    j = 1

    while j * j <= i:
        dp[i] = min(dp[i], dp[i - j * j] + 1)
        j += 1

print(dp[n])

 
時間の複雑さ