2021_07_24 山田 ABC210 D 解説

スライド

問題

動的計画法（DP）

って何？　👉　直接計算すると大きな時間がかかってしまう問題に対し、途中の計算結果をうまく再利用することで計算　　効率を上げる手法のこと

https://scrapbox.io/files/60f7c2422b0fb10023f3d583.png

パターン

https://scrapbox.io/files/60f7c5fdd4ed71001c4ffe2a.png

矩形領域

https://scrapbox.io/files/60f7e18aaec781001ca31c60.png

ACコード（Python）

code:python

h, w, c = map(int,input().split())

A = []

for i in range(h):

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

A.append(array)

INF = int(1e18)

ans = INF

for _ in range(2):

# dpijはi,jのときのAij - c*(i+j)の最小値

dp = [INF for _ in range(w) for _ in range(h)]

for i in range(h):

for j in range(w):

if i > 0:

dpij = min(dpij, dpi-1j)

if j > 0:

dpij = min(dpij, dpij-1)

ans = min(ans, Aij + c*(i+j) + dpij)

dpij = min(dpij, Aij - c*(i+j))

A.reverse()

print(ans)

参考