[学習記録]AtCoder EDP A-Frog 1 [Go]

問題文

N 個の足場があります。 足場には 1,2,…,N と番号が振られています。 各 i (1≤i≤N) について、足場 i の高さは hi​ です。

最初、足場 11 にカエルがいます。 カエルは次の行動を何回か繰り返し、足場 N まで辿り着こうとしています。

• 足場 i にいるとき、足場 i+1 または i+2 へジャンプする。 このとき、ジャンプ先の足場を j とすると、コスト ∣hi​−hj​∣ を支払う。

カエルが足場 N に辿り着くまでに支払うコストの総和の最小値を求めてください。

解法

iの足場につくためのコストの総和の最小がわかればいい
i の足場には i -1, i -2からしか来れないので、

// コストを計算
c1 := dp[i-1] + Abs(sli[i-1]-sli[i])
c2 := dp[i-2] + Abs(sli[i-2]-sli[i])

// 小さいほうを保持
dp[i] = Min(c1, c2)

i = 1の時はi = 0からの繊維しかないため、dp[1]にはそのままコストを入れる

dp[1] = Abs(sli[0] - sli[1])

i = 2より、すべての i について計算し、dp[n -1]が回答になる（n番目の足場の最小値）

コード（AC)

func run() interface{} {
	n := readInt()

	sli := readSli(n) // save cost

	dp := make([]int, n)
	dp[1] = Abs(sli[0] - sli[1])
	for i := 2; i < n; i++ {
		c1 := dp[i-1] + Abs(sli[i-1]-sli[i])
		c2 := dp[i-2] + Abs(sli[i-2]-sli[i])
		dp[i] = Min(c1, c2)
	}

	ans := dp[n-1]
	return ans
}