Dynamic Programming (DP)

コメントブログ

ダイナミックプログラミングとは?

ダイナミックプログラミング(Dynamic Programming,DP)アルゴリズムは、メモリ容量を少なくしながら演算速度を高速に増加させる技術である.

計算された結果(小さな問題)は、再計算を回避するために個別のメモリ領域に格納されます.

動的プログラミングの実施は、通常、上から下へおよび下から上への方式を採用する.

条件

動的プログラミングは、次の条件を満たすために使用できます.

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

同じ小さな問題を繰り返し解決する必要がある.

注記構造

注記は、ダイナミックプログラミングを実現する方法の1つです.

は、計算結果をメモリ領域に記録する方法である.

同じ問題を再度呼び出すと、コメントの結果が直接得られます.

記録値の観点からキャッシュとも呼ばれる.

注釈は、一度に取得された情報をリスト形式で格納することができるようになった.

このリストは、通常、DPテーブルと呼ばれる.

上下逆さ

バックグラウンド方式は再帰関数で実現でき,バックグラウンド方式は繰り返し文で実現できる.
ダイナミックプログラミングの典型的な形式はスタンド方式である.
どちらがいいかは、問題ごとに違います.ただし、通常の再帰関数を使用するよりも、重複文を使用する方がパフォーマンスが優れています(オーバーヘッドが小さいため).時間の複雑さの面では同じです.
そのため、特定の場合を除いて、自分の気持ちのいいものを使えばいいのです.
フィボナッチ数列問題は動的プログラミング技術によって効率的に解くことができる問題の一つである.
フィボナッチ数列問題を通してDP問題の流れを理解しよう.
まず、次のようにフィボナッチ数列を点火式で表します.
a[n] = a[n-1] + a[n-2],
a[1] = 1, a[2] = 1
n次フィボナッチ数=(n-1)次フィボナッチ数+(n-2)次フィボナッチ数
99番目のフィボナッチ数列を求める場合は、DP方式を用いずに再帰関数を用いて以下のように解決する.

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

print(fibo(99))

これにより,nが大きいほど計算された関数が繰り返し呼び出されるため,実行時間は幾何級数で増加する.
これらの問題にダイナミックプログラミング技術を採用することで、時間を大幅に短縮することができる.

上から下へのコードの使用

DPテーブルの初期化（1から99までとする）

d = [0] * 100

再帰関数でフィボナッチ関数(タワー)を実現する

def fibo(x):

    # 종료 조건(1 또는 2일때 1을 반환)
    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))

網掛けコード

DPテーブルの初期化

d = [0] * 100

1番目のフィボナッチ数と2番目のフィボナッチ数は1です

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])