面接準備/アルゴリズム7/ダイナミックプランニングと分割征服

ダイナミックプランニングと分割

1.定義

動的計画法(DPと呼ぶ)

アルゴリズムは,小部分入力問題を解決した後,この部分問題の解を用いて,大部分の問題を解決し,最終的に全体の問題を解決する.

は、最下位レベルの答えを見つけて保存し、結果値を使用して最上位レベルの問題

を解く上向きの方法である.

Memoizationテクノロジーの使用

Memoization(注記アニメーション)は、プログラムの実行時に以前に計算した値を保存することで、再計算を回避し、全体の実行速度を速める技術です.

の問題を分割する時、一部の問題は繰り返して、回収することができます

例:フィボナッチ数列

分割征服
アルゴリズム

は、問題をいくつかの部分に分けてから、結合して問題の答えを得る.

下梁式の解法、上、下を求めます

は通常、再帰関数を用いて

を実現する.

問題を細分化する場合、一部の問題は重複しない

の例:

(連結ソートやクイックソートなど)

2.異同

共通点

の問題を最小のユニット

に分割する.

差異

動的計画法

の一部の問題は冗長であり、親の問題を解決する際に

を再利用することができる.

Memoization技術(一部の問題の答えを記憶と回収の最適化技術とする)

を用いる.

分割征服

一部の問題は互いに重複しない

Memoization技術

を使用しない

3.動的計画アルゴリズムの理解

プログラミング練習
フィボナッチ数列:nを入力し、以下のように計算します.
nを入力すると、結果値がフィボナッチ数列で出力されます.

함수를 fibonacci 라고 하면,
fibonacci(0):0
fibonacci(1):1
fibonacci(2):1
fibonacci(3):2
fibonacci(4):3
fibonacci(5):5
fibonacci(6):8
fibonacci(7):13
fibonacci(8):21
fibonacci(9):34

再帰呼び出しの使用

def fibo(num):
    if num <= 1:
        return num
    return fibo(num - 1) + fibo(num - 2)

fibo(4)

3

ダイナミックプランニングの活用

def fibo_dp(num):
    cache = [ 0 for index in range(num + 1)]
    cache[0] = 0
    cache[1] = 1
    
    for index in range(2, num + 1):
        cache[index] = cache[index - 1] + cache[index - 2]
    return cache[num]

fibo(10)

55

実行コードの表示と理解:グーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグーグー

分割征服アルゴリズムの例は,単独の章で紹介したマージソートと高速ソートによって理解される.