[白俊]1699:平方和(Python)

3245 ワード
algorithm テキストリンク

質問する📖



に答える🙏

  • 平方数がiより大きい場合は重複文は実行しない.
  • 平方数で表す場合、最も少ない数のjを探す.
  • dp[i] = dp[i-j*j]+1中+1の原因はj平方数加算である.

    • コード#コード#💻

    n = int(input())
dp = [0] * (n+1)
for i in range(1,n+1):
    dp[i] = i
    for j in range(1, i):
        # 제곱수가 i보다 커지면 멈춤
        if j*j > i:
            break
        # 제곱수로 표현할 때 가장 항의 개수가 작은 j를 찾음
        # 예를 들어 dp[6] = dp[6 - 2*2] + 1 은 2*2를 더한 경우 1가지를 추가하기 때문.
        if dp[i] > dp[i-j*j] + 1:
            dp[i] = dp[i-j*j] + 1
print(dp[n])
    2018テンセント実習生募集筆記試験問題
    [Git] git workflow & rebase