ダイナミックプログラミング

動的計画法と呼ばれるdpアルゴリズムはdynamicとは何の関係もない.
韓国語で覚えた方がわかりやすい翻訳です.
この方法では、計算された値を繰り返し計算するのではなく、保存された値(コメントされた値)から取得し、時間の複雑さを低減します.
複数の与えられた問題 部分的な問題に分けて解決し、結果で与えられた問題を解決します.一部の問題では,重なる部分にメモを書き,そこで時間の複雑さを減らす.
ex)fibonacciを再帰的に実現し、以下に示す

def f(n):
    if n <= 1:
        return n
    return f(n-2) + f(n-1)

f(10)が呼び出されると、呼び出されたf(0)~f(8)が複数回呼び出される.
n=10の場合、この値は小さく見えるかもしれないが、nが大きくなると、f(0)を繰り返し呼び出す回数が指数関数的に増加するため、dpを用いてこの問題を解決する.

10
F(10): 55
호출 횟수
F(0): 34회 호출
F(1): 55회 호출
F(2): 34회 호출
F(3): 21회 호출
F(4): 13회 호출
F(5): 8회 호출
F(6): 5회 호출
F(7): 3회 호출
F(8): 2회 호출
F(9): 1회 호출
F(10): 1회 호출

ex)fibonacciをdp(top-down,再帰)に実現

memo = [-1 for _ in range(N+1)]
memo[0] = 0
memo[1] = 1

def fibo(n):
	# 이미 계산해놓은 값은 다시 계산하지않고, 저장해놓은 값에서 가져와서 return
	if memo[n] != -1:
		return memo[n]
	else: # 아니라면, 계산후 memo하고 return
		memo[n] = fibo(n-1) + fibo(n-2)
		return memo[n]

N = int(input())
print(fibo(N))

ex)fibonacciをdp(bottom-up,繰返し)に実現
bottom-up

N = int(input())
memo = [0 for _ in range(N+1)]
memo[1] = 1

for i in range(2,N+1):
	memo[i] = memo[i-1] + memo[i-2]

print(memo[N])

ex)1463,1

import sys
input = lambda : sys.stdin.readline().rstrip()

N = int(input())
dp = [10**8 for _ in range(10**6+1)]
dp[1] = 0
for i in range(1,N):
    dp[i+1] = min(dp[i+1],dp[i] + 1)
    if i*3 <= N:
        dp[i*3] = min(dp[i*3],dp[i] + 1)
    if i*2 <= N:
        dp[i*2] = min(dp[i*2],dp[i] + 1)

print(dp[N])

top-down
再帰解を使うとこうなりますが、メモリを超えてしまいます.Nが最大値であれば,再帰深さが最低10**6であるためかもしれない.

import sys
sys.setrecursionlimit(10**7)

N = int(input())
dp = [-1 for _ in range(N+1)]
dp[1] = 0

def solve(n):
    if dp[n] != -1:
        return dp[n]
    else:
        dp[n] = solve(n-1) + 1
        if n % 3 == 0:
            dp[n] = min(dp[n], solve(n//3) + 1)
        if n % 2 == 0:
            dp[n] = min(dp[n], solve(n//2) + 1)
        return dp[n]

print(solve(N))