[伯俊]#1463-1制作

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

1として作成


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

私が書いたコード


BFSを用いてリリースした.
from collections import deque


n = int(input())


def bfs(x):
    q = deque([x])
    visited = [-1] * (x + 1)
    visited[x] = 0

    while q:
        x = q.popleft()

        if x == 1:
            return visited[x]

        if x % 3 == 0 and visited[x // 3] == -1:
            q.append(x // 3)
            visited[x // 3] = visited[x] + 1
        if x % 2 == 0 and visited[x // 2] == -1:
            q.append(x // 2)
            visited[x // 2] = visited[x] + 1
        if visited[x - 1] == -1:
            q.append(x - 1)
            visited[x - 1] = visited[x] + 1


print(bfs(n))

動的プログラミングを使用したコード


解題後はダイナミックプログラミングに分類されるので,ダイナミックプログラミングで再解題する.
BFSではnから計算を開始し,DPでは1から計算を開始する.
採点の結果,BFSを上で用いたコードは,DPを下で用いたコードよりも速かった.
DPのコードを使用してすべての場合に比較計算を行うには、より長い時間がかかる場合があります.
n = int(input())

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

print(dp[n])
Blockの本質
ThreadLocal学習資料