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

メモリを使用して、実行時間の効率を迅速に向上させる方法

計算結果は、独立したメモリ領域

に記憶する.

の実施は、通常、2つの態様(タワーおよび寝台)からなる:

.

ダイナミックプランニング法とも呼ばれます.

典型的なプログラミング分野におけるダイナミックとは何ですか.

プログラム実行中に実行に必要なメモリを割り当てる技術

一方,動的プログラミングで用いられる語には何の意味もない.

実施条件

1.最適な局所構造
大きな問題は小さな問題に分けることができ、小さな問題の答えは集中して大きな問題を解決することができる.
2.重複部分の問題
同じ小さな問題を繰り返し解決する必要がある場合

代表的な問題

フィボナッチ数列

1,1,2,3,5,8,13,21,34,55,89,...
n個の数は、n−1とn−2個の数の和を示す数列である.
1+1= 2 , 1+2= 3, 2+3=5
フィボナッチ数列問題は動的プログラミングを用いた典型的な問題の一つである.
動的プログラミングがいつ使用されるかを知るためには、上記の実施条件が適用されるかどうかを決定する必要がある.
1.最適な局所構造
例えば、フィボナッチ数列の5番目の数字を知りたいなら
1+1=2(3番目)、1+2=3(4番目)、2+3=5(5番目)、正解は5
5番目の式を見ると、2(3番目)+3(4番目)になります.
5番目の大きな問題を3番目と4番目の2つの問題に分けて解くことができ,統合することができるので,最適な局所構造に非常に適している.
2.重複する部分的な問題
前に示したように、3番目の4番目を分けて、問題を解くときに重複する部分があることを確認します.
1+2=3(4番目)のプールの2は実際には3番目のプールの結果である.
3番目のプールがこの値をメモリに格納している場合、4番目のプールには3番目のプールは必要ありません.このメソッドは、以下に説明するアノテーション作成と呼ばれます.
点火式:隣接項間の関係式

# 재귀 함수로 구현
def fibonacci(n):
    if n == 1 or n == 2:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

上記の単純な再帰関数を用いて解くと,指数時間の複雑さがある.(O(2^n))
以下に示すように、f(2)が複数回呼び出されたことを確認することができる.(冗長性の問題)
f(30)の計算には約10億回の演算が必要である.
実施条件が満たされていることを確認する
1.最適な局所構造
2.重複する部分的な問題

注記構造

計算結果をメモリ領域に書き込む方法

などの問題を再度呼び出すと、記録した結果が得られます.

レコード

の値もキャッシュと呼ばれます.

タワーとタワーがあります.

タワー

下から上へとも呼ばれています.

ベースフレーム

上向きともいう.
動的プログラミングの典型的な形式は基礎的なプログラミングである.

結果を保存するためのリスト(配列)をDPテーブルと呼ぶ.

注記分解を使用したフィボナッチ数列(タワー)

d = [0] * 100

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

昇格を使用してフィボナッチ数列を解く

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

まず小さな問題を解決してから大きな問題を解決する過程.

どうさぶんせき

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

両方とも最適なローカル構造を持つ場合に使用できます.최적 부분 구조大問題を大々的にやる
違いは一部の問題の繰り返しです!
動的プログラミング問題では,各局所問題は相互に影響し,一部の問題は重複している.
分割征服問題は同じ部分の問題を繰り返し計算しない.

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

で与えられた問題がダイナミックプログラミングタイプであることを理解することが重要です.

まず、図面、実装、完全なナビゲーションなどの方法によって問題を解決できるかどうかを審査する

.

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

である.

コットでは、基本的なタイプのダイナミックプログラミングの問題がよく発生します.