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

ダイナミックプログラミングの条件

最適局所構造
大きな問題は小さな問題に分けることができ、小さな問題の答えは集中して大きな問題を解決することができる.

部分問題の繰り返し
同じ小さな問題は繰り返し解決しなければならない.

フィボナッチの数列などを救いたいときは、試してみてください.

def fibo(x):
	if x == 1 or x == 2:
    	return 1
	return fibo(x-1) + fibo(x-2)
print(fibo(4))

注記構造

注記ダイナミックプログラミングを実現する方法の1つです
計算結果をメモリ領域に書き込む方法
同じ問題を再度呼び出すと、コメントの結果が直接得られます.
記録値の観点からキャッシュとも呼ばれる.

Top down vs Bottom up

上から下へ
DPの典型的な形式はBoottom up方式である.
結果を保存するためのリストをDP Tableと呼びます.

DPでフィボナッチ数列を求め、

dp = [0] * 100 # 메모이제이션으로 우선 100개의 원소를 가진 결과값을 초기화해놓는다.
def fibo(x): # 재귀함수로 구현한 피보나치 함수
	if x == 1 or x == 2:
    	return 1
    if dp[x] !=0: # 계산이 되었다면 무조건 배열의 원소는 0이 아니게 되므로 계산된적이 있다면 그대로 반환해준다.
    	return dp[x]
    dp[x] = fibo(x-1) + fibo(x-2) # 계산이 되지 않은 경우
    return dp[x]
print(fibo(99))

Boottom upでDPでフィボナッチ数列を求める

dp = [0] * 100 # 계산결과를 저장하기위해 모든 배열을 0으로 초기화해서 저장함.

dp[1] = 1
dp[2] = 1
n = 99

for i in range(3,n+1): # 반복문으로 구현해서 결과값들을 저장해놓는다.
	dp[i] = dp[i-1] + dp[i-2]
print(dp[n])

このように注釈を利用すると,時間的複雑度がO(N)となる.

ダイナミックプログラミングvs分割征服

動的プログラミングおよび分割征服は、最適なローカル構造を有する場合に使用することができる.
大問題を大々的にやる
動的プログラミングと分割征服の違いは局所問題の繰返し性にある.
動的プログラミング問題では,各部分の問題が相互に影響し,一部の問題が繰り返される.
分割征服問題では,同じ部分の問題を繰り返し計算することはない.

動的プログラミングの問題の処理方法

GRADY、実装、完全なナビゲーションなどの考え方で問題を解決できるかどうかを確認する必要があります.
低効率な完全なナビゲーションプログラムを再帰関数で記述し、小さな問題の答えが大きな問題で使用可能である場合は、コードを改善する方法を使用します.
アリ問題

import sys

n = int(sys.stdin.readline()) 
li = list(map(int,sys.stdin.readline().split()))

dp = [0] * 100

dp[0] = li[0]
dp[1] = max(li[0],li[1])
for i in range(2,n):
    dp[i] = max(dp[i-1],dp[i-2]+li[i])
print(dp[n-1])

1として作成

import sys

x = int(sys.stdin.readline())

dp = [0] * 30001

for i in range(2,x+1):
    dp[i] = dp[i-1] + 1

    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)
    if i % 5 == 0:
        dp[i] = min(dp[i],dp[i//5]+1)
print(dp[x])

効率的な通貨構成

import sys

n,m = map(int,sys.stdin.readline().split())

li = [int(input()) for _ in range(n)]

inf = sys.maxsize
dp = [inf] * (m+1)
dp[0] = 0
for i in range(n): # i는 화폐 단위를 의미하고
    for j in range(li[i],m+1): # j는 금액을 의미한다. 해당 금액인 li[i] 부터 m원까지를 확인한다.
        if dp[j-li[i]] != inf: # 현재 금액에서 현재 확인하고있는 화폐 단위의 금액을 뺸 것을 만들 수 있다면
            dp[j] = min(dp[j],dp[j-li[i]]+1) # 점화식 계속 최소값으로 갱신되는 방식

if dp[m] == inf:
    print(-1)
else:
    print(dp[m])

金鉱問題

import sys

t = int(sys.stdin.readline())

for _ in range(t):
    n,m = map(int,sys.stdin.readline().split()) # 3,4
    li = list(map(int,sys.stdin.readline().split())) # 1 3 3 2 2 1 4 1 0 6 4 7

    dp = []
    index = 0
    for i in range(n):
        dp.append(li[index:index+m])
        index += m
    #print(dp)

    for j in range(1,m):
        for i in range(n): # 모든 행 위치에 대해서
            if i == 0: # 왼쪽 위
                left_up = 0
            else:
                left_up = dp[i-1][j-1]
            if i == n-1: # 왼쪽 아래
                left_down = 0
            else:
                left_down = dp[i+1][j-1]
            
            left = dp[i][j-1] # 왼쪽
            dp[i][j] = dp[i][j] + max(left_up,left_down,left)
    result = 0
    for i in range(n):
        result = max(result,dp[i][m-1])
    print(result)
            

兵士配置問題

import sys

n = int(sys.stdin.readline())

li = list(map(int,sys.stdin.readline().split()))

li.reverse() # 가장 긴 증가하는 수열을 만들기 위해서 

dp = [1 for _ in range(n)] # li[i] 를 마지막 원소로 가지는 부분 수열의 길이

for i in range(1,n):
    for j in range(i):
        if li[j] < li[i]:
            dp[i] = max(dp[i],dp[j]+1)
print(n - max(dp))

ソース:https://freedeveloper.tistory.com/276