[伯俊/Python]制作14631

3796 ワード
アルゴリズム#アルゴリズム# ダイナミックプログラミング テキストリンク

https://www.acmicpc.net/problem/1463

アルゴリズム分類

  • 動的プログラミング

    • 問題を解く


    ダイナミックプログラミングの典型的な問題.
    グリディのやり方で近づくことはできない.
    d[i]iを1にした演算回数を記憶する.
    d[0]またはd[1]の演算回数は0であるため、1とする.
    nが10の6乗の場合のインデックスは10の6乗であるため,dの範囲は10**6+1である.

    ソースコード

    n=int(input())
d=[0]*(10**6+1)

for i in range(2, n+1):
  d[i]=d[i-1]+1
  if i%2==0:
    d[i]=min(d[i], d[i//2]+1)
  if i%3==0:
    d[i]=min(d[i], d[i//3]+1)

print(d[n])
    [TIL]カゼ黒
    1つのActivityで2つのlayoutインスタンスを使用