DP A

スタートからゴールへ行く

各点で1つ進むか2つ進むかの2通りの選択肢があり、それによってコストが異なる

ゴールに至る最小コストを求める問題

各点を定義域とし、そこに至る最小コストを値とするDP

DP_A

code:python

def solve(N, heights):

for i in range(2, N):

)

「今入ってる値と、新しい値の小さい方を選ぶ」という書き方のため、十分大きな値INFで初期化している

実はこの問題に関しては2つ目のminで常に新しい値が小さいし、必ず最初に更新されるので、ここをminでなくして、コストを初期化しなくしてもよい

iがゴールの直前まで走る必要があるのに、2つ先まで参照するので、範囲外アクセスを避けるために一つ大きく確保する必要があった

これに相当することは集めるDPでは「0と1を事前に計算」「ループを2から始める」という形で対処している

個人的には、ちょっと頭をひねる必要がある感じ

code:python

def solve(N, heights):

for i in range(N - 1):

これは素直

どの値が計算済みかはメモ化の部分に押しつけて、人間は気にしていない

計算済みかどうかを識別できる必要があるので、コストとしてあり得ない値(None)で初期化してある

code:python

def solve(N, heights):

def get_cost(i):

c = min(

)

return c

return get_cost(N - 1)