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

コンセプト

動的プログラミングで適切なメモリを使用して実行時間を節約する方法

計算された結果は、再計算を回避するために独立したメモリ領域に格納されます.

はタワーとタワーの2種類に分けられます:

条件

1.最適な局所構造

大きな問題は小さな問題に分けることができ,小さな問題の答えは集中して大きな問題を解決することができる.

2.重複する部分的な問題

同じ小さな問題を繰り返し解決しなければならない.

例

フィボナッチ数列

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

print(fibo(4))

同様に,フィボナッチ数列を再帰的に解くと,不要な関数呼び出しが多くなる.この場合,時間的複雑度がO(2^n)の複雑度が現れる.では、時間の複雑さを減らすにはどうすればいいのでしょうか.

ダウンタイム（注記作成）

計算結果をメモリ領域に書き込みます.キャッシュとも呼ばれます.

d = [0] * 100

def fibo(x):
	if x == 1 or x == 2:
    	return 1
	if d[x] != 0:
    	return d[x]
	d[x] = fibo(x-1) + fibo(x-2)
    return d[x]

print(fibo(99))

時間的複雑さをO(N)に低減できる.

基準アップ（DPテーブル）

d = [0] * 100

d[1] = 1
d[2] = 1
n = 99

for i in range(3, n + 1):
	d[i] = d[i-1] + d[i-2]

print(d[n])

問題の処理方法

与えられた問題が動的プログラミングタイプであることを決定することは重要である

まず、お客様の考えを確認します.

再帰関数を用いて効率の低い完全なナビゲーションプログラム(topdown)を記述すると、小さな問題の答えが大きな問題で依然として利用可能である場合、改良コードの方法

を用いることができる.

の通常の符号化テストレベルでは、通常、基本的なタイプの動的プログラミング問題

が発生する.

例

1.

💡 アイデア

各ビット数まで略奪できる値を含むリストを作成します.そして、アップグレードで問題を解決します.

n = int(input())
array = list(map(int, input().split()))

d = [0] * 100

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

2.

💡 アイデア

この問題もアップグレードで解決しなければならない.1～Xの最小演算回数を含むDPテーブルを作成して問題を解決します.
この場合、26であれば、−1の後のd[25]と2で割ったd[13]とを予め求めることができ、この2つの演算のうちのどちらが後の方がより効率的なスキームであるかを求めることができる.

x = int(input())

d = [0] * 30001

for i in range(2, x+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)
	if i % 5 == 0:
    	d[i] = min(d[i], d[i//5] + 1)

print(d[x])

3.

💡 アイデア

図に示すように、まずリスト値の初期化を行います.そして各通貨の価格更新と同時に問題を解決すればよい.

N, M = map(int, input('입력 = ').split())
X = list()
for i in range(N):
    X.append(int(input()))

d = [10001] * (M + 1)

d[0] = 0
for i in range(N):
    for j in range(X[i], M+1):
        if d[j - X[i]] != 10001:
            d[j] = min(d[j], d[j - X[i]] + 1)

if d[M] == 10001:
    print(-1)
else:
    print(d[M])

4.

💡 アイデア

dpテーブルのdを0に初期化し,これは2次元空間の問題であるため,方向ベクトルを定義した.
また,第1列はarrと同じ値であるため初期化を行う.
2階建てforゲートでは、各列の行がアクセスされます.現在の位置に我々が定義した3つの方向が範囲を超えない場合、移動位置のdpテーブル値と移動前のdpテーブル値+移動位置のarr値を比較し、両者のうちより大きなものを移動位置のdpテーブルに格納する.
これにより、現在位置が移動している3つの位置の値が比較され、値が大きい場合はdpテーブルの値が更新されます.

row, column = map(int, input().split())
arr = list()
for i in range(row):
    arr.append(list(map(int, input().split())))

d = [[0] * column for _ in range(row)]

dRow = [-1, 0, 1]
dColumn = 1

for i in range(row):
    d[i][0] = arr[i][0]

for i in range(column):
    for j in range(row):

        for k in range(len(dRow)):
            movedRow, movedColumn = j + dRow[k], i + dColumn
            if movedRow < 0 or movedRow >= row or movedColumn < 0 or movedColumn >= column:
                continue
            d[movedRow][movedColumn] = max(d[movedRow][movedColumn], d[j][i] + arr[movedRow][movedColumn])

for i in range(len(d)):
    for j in range(len(d[i])):
        print(d[i][j], end=' ')
    print()

print(max(list(map(max, d))))

5.

💡 アイデア

この問題はLISで簡単に解決できる.逆入力arrはLIS問題と同じなので使用します.

n = int(input('입력 = '))
arr = list(map(int, input().split()))
arr.reverse()

d = [1] * (n + 1)

for i in range(1, n):
    for j in range(i):

        if arr[j] < arr[i]:
            d[i] = max(d[i], d[j]+1)

print(n - max(d))