Frog問題を勉強してみた

導入

Frog問題について勉強してみた.

Frog問題

N = int(input())
h = [int(x) for x in input().split()]
dp = [0]*N
dp[0] = 0
dp[1] = abs(h[1] - h[0])
for i in range(2, N):
    dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]))
print(dp[N - 1])

解法の考え方

Step1. 値格納用のlistを作製する

Step2. 決まり切っている値を代入する
ここではdp[0]には0,dp[1]には一つ進む以外ないのでdp[1]=abs(h[1]-h[0])しかない

Step3. 各状況においてmin()関数を使って最小の状況を求める
ここではforループを用いてiを目標座標として二つのパターンにおけるスコアを求める。そのスコアが最小の方をそのその状況の最小のスコアとする。