[伯俊][Python]1463号:1制作

4517 ワード
白駿 パイ テキストリンク

これは理解しにくい問題です…!
ダイナミックプランニング(Dynamic Programming)、dpのタイプ.
基本的には「点画式」を実現する方法ですが、他の人は私が最近実現とシミュレーションを主として勉強している理由が分からないのではないでしょうか.難しすぎます...
n = int(input())
dp = [0 for _ in range(n+1)]
#여기서 dp[n] 는 n을 1로 만드는 최소한의 계산 횟수를 의미합니다.
for i in range(2, n+1):
    #1은 계산을 실행하지 않아도 1이기 때문에 1에서는 0이고, 2에서부터 시작합니다.
    #range를 사용할 경우 끝나는 값에 -1이 추가되기 때문에 n+1로 설정하였습니다.
    dp[i] = dp[i-1] + 1
    #일단 dp라는 리스트를 1부터 n까지의 수로 이루어진 리스트로 만들어줍니다.
    if i%2 == 0:
        dp[i] = min((dp[i]), dp[(i//2)]+1)
    if i%3 == 0:
        dp[i] = min((dp[i]), dp[(i//3)]+1)
    #이전 값까지 계산된 횟수에서 계산을 한번 더 하면 마지막 값이 나온다! 라는 개념.
print(dp[n])
コメントで説明しましたが、私自身も概念を再整理しておけば、
*リストのn番目のカウントは、if文で実現されたドアの点火方式で計算されたときの最小カウントを表します.
*したがって、i/2、i/3個あたりの「数値」の最小計算回数+1となる.
*簡単に言えば、リストには、最終的に得られた1から与えられた値までの遡及回数が最も少ない値dpがリストされる.
スレッド起動
[アルゴリズム]偽装プログラマー(Python)