[アルゴリズム]動的プログラミング

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

一つの問題は一度だけ解くアルゴリズムです.

解法:
小さな質問は一度しか答えられませんので、正しい答えを見つけた小さな質問をメモしてください(コメントとしても構いません)
大きな問題を解く場合,同じ小さな問題が発生すると,小さな問題の結果値を利用する.

条件:
小さな問題が繰り返されると、
同じ問題は,解くたびに結果値が同じである.

例えば、白砂糖配送の問題を利用してDPを分析する

問題の説明

尚根は最近砂糖工場で砂糖を送った.尚根は今、キャンディ屋に正確にNキロの砂糖を送る.砂糖工場で生産された砂糖は袋に入っている.袋は3キロ袋と5キロ袋があります.
尚根は面倒なので、できるだけ少ない袋を持っていきたいと思っています.例えば、18キロの砂糖を配達する必要がある場合は、3キロの袋を6つ持ってもいいですが、5キロと3キロを3つ配達すれば、より少ない数の袋を配達することができます.

初期実装コード(グリンディ)

n = int(input())

result = []

d = n // 5
y = 0

// 5키로짜리 봉지를 사용가능한 갯수를 0까지 반복
for i in range(d,-1,-1):
  res = n - (i * 5)
  if res % 3 == 0:
    print(i+(res//3))
    y = 1
    break

if y == 0:
  print(-1)

Greedoで実現することもできますが、dpで解決することができます.

インプリメンテーションコード(ダイナミックプログラミング)

3 -> 1
4は-1、X
5 -> 1
これらの3と5の数字の間に3,5の差がある数字は、以前の値に1を加えればよい.
すなわちdictionaryを用いて表を作成し,対応する数字を記入して値を導出する方式である.

n = int(input())

result = []

res = {3:1,5:1}

for i in range(6,n+1,1):
  tmp = 0
  if i-3 in res.keys() and i % 5 != 0:
    tmp = res[i-3]+1
  elif i-5 in res.keys():
    tmp = res[i-5]+1

  if tmp != 0:
    res[i] = tmp

if n in res.keys():
  print(res[n])
else:
  print(-1)

この解法は既に計算済みの問題を解決しており,追加するだけでよいので,複数回計算を繰り返す必要はない.

動的プログラミングの問題タイプ

プログラマーレベル3.せいすうさんかくけい
問題の説明
上の三角形の上部から下部へのパスでは、最大のマージ数を検索します.セルを下に移動する場合は、1つのセルの右または左側のみが対角線方向に移動できます.たとえば、3では、次のセルの8または1にのみ移動できます.
三角形情報を含む配列三角形をパラメトリック化する場合は、解いた関数を完了して、経過した数値の最大値を返します.
どうてきプログラミングほう
過去の数字の和は最大の状況を探す問題だ.
この問題は2段三角形か8段三角形ですが、同じ位相の数字が1の場合、その数字を取り、2つの場合、もっと大きな数字を取ります.
したがって,同じ問題を繰り返さない動的プログラミングを用いて,親の数字に自分の数字を加えることができる.

def solution(triangle):
    answer = 0
    
    for i in range(1,len(triangle)):
        for index,data in enumerate(triangle[i]):
            // 인덱스가 0인 경우
            if index == 0:
                triangle[i][index] = data + triangle[i-1][index] 
            // 인덱스가 마지막 번호인 경우
            elif index == i:
                triangle[i][index] = data + triangle[i-1][index-1]
            //중간 인덱스인 경우 둘 중 큰수를 자신에게 대입한다.
            else:
                triangle[i][index] = data + max([triangle[i-1][index-1],triangle[i-1][index]]) 
        
    return max(triangle[len(triangle)-1])

プログラマーレベル3.通学路
問題の説明
持続的な豪雨が一部の地域を水没させた.水没していない地域を通って学校に行きたいです.家から学校までの道はm×nサイズのグリッドで表すことができます.
下図はm=4,n=3である.
最左上隅(すなわち家屋の所在地の座標)は(1,1)であり、最右下角(すなわち学校の所在地の座標)は(m,n)である.
グリッドサイズm、n、および水没領域座標を含む2 Dフラットピットにパラメータ化します.右側と下側だけに移動し、家から学校までの最短パスの数を1000000 7で割ってからソリューション関数に戻ってください.
どうてきプログラミングほう
4*3座標の各座標の最短経路は,計算した最短経路で最終目的地の最短経路を求める.
座標と同じサイズの配列を作成し、障害物座標を-1に指定します.
右と下にしか移動できないので、計算には上と左の座標の最短パスを使用します.

def solution(m, n, puddles):
    answer = 0
    
    arr = list(list(0 for i in range(m)) for i in range(n))
    
    for i in puddles:
        arr[i[1]-1][i[0]-1] = -1
    
    arr[0][0] = 1
    
    for i in range(n):
        for j in range(m):
            
            if arr[i][j] != -1:
            	// 왼쪽 좌표
                if j >= 1 and arr[i][j-1] != -1:
                    arr[i][j] += arr[i][j-1]
                // 위쪽 좌표
                if i >= 1 and arr[i-1][j] != -1:
                    arr[i][j] += arr[i-1][j]
                    
    return arr[n-1][m-1] % 1000000007

ダイナミックプログラミングを学んだ後の感想

小さな問題をうまくつかんで何度も繰り返しなければならない.

グラフィックで問題を解決するにはDP方式を考慮する必要がある.
図形問題は小図形と大図形の解法とほぼ同じであるからである.
dpを利用して近づくべきだ.

グリディ方式で解決できない場合は、小さな範囲で得られた結果をリストし、前の解決方式を利用できるかどうか、重複した式があるかどうかを分析します.

多くの問題が発生し,想像以上に容易な問題も動的プログラミングで解決できるようになった.いろいろな方法のアルゴリズムでそれに近づく練習をします.