[学習記録]AtCoder EDP B-Frog 2[Go]

問題文

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

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

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

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

解法

基本的にはA-Frog 1 と同じ解法でいけるが、ジャンプできる足場の数がK個あるので、ここをループによって求める。
i - j < 0 となったとき、足場が存在しないため、ループを終了する

	for i := 1; i < n; i++ {
		for j := 1; j <= k; j++ {
			if i-j < 0 {
				break
			}

			dp[i] = Min(dp[i-j]+Abs(sli[i-j]-sli[i]), dp[i])
            // same as below
            // before := dp[i-j] + Abs(sli[i-j] - sli[i])
            // dp[i] = Min(before, dp[i])
		}
	}

dpが0で初期化されているため、このままだと必ずMin(before, dp[i]) = ０となり、計算できない。そのため、ガードを入れることで計算を続行する

if dp[i] == 0 {
	dp[i] = dp[i-1] + Abs(sli[i-1]-sli[i])
	continue
}

Frog 1 と同様に、dp[n -1]が答えになる

コード（AC)

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

	sli := readSli(n)
	dp := make([]int, n)

	for i := 1; i < n; i++ {

		for j := 1; j <= k; j++ {
			if i-j < 0 {
				break
			}

			if dp[i] == 0 {
				dp[i] = dp[i-1] + Abs(sli[i-1]-sli[i])
				continue
			}

			dp[i] = Min(dp[i-j]+Abs(sli[i-j]-sli[i]), dp[i])
		}
	}
	ans := dp[n-1]
	return ans
}