【AtCoder】Educational DP Contest B - Frog 2 【python】

アルゴリズム実技検定 公式テキスト (エントリー～中級編)の6.4.1 で Educational DP Contest A - Frog 1
の類題として挙げられている問題を解いてみました。
Educational DP Contest B - Frog 2
submission

N, K = map(int, input().split())
h = list(map(int, input().split()))

cost = [float('inf')] * N
cost[0] = 0

for i in range(1, N):
    for j in range(1, K+1):
        if i - j >= 0:
            cost[i] = min(cost[i], cost[i-j] + abs(h[i-j] - h[i]))

print(cost[N-1])

元の問題とは違いジャンプ元の候補がKあるためforループを使用し解きました。
動的計画法にも少しずつ慣れていきたいです。

メモ化再帰
参考
https://github.com/kenkoooo/pastbook-source-code/blob/master/chukyu/python/chapter06/section04/6-4-3.py

import sys
sys.setrecursionlimit(1000000)

N, K = map(int, input().split())
h = list(map(int, input().split()))

cost = [float('inf')] * N
cost[0] = 0

done = [False] * N

def rec(i):
    if done[i]:
        return cost[i]


    for j in range(1, K+1):
        if i - j >= 0:
            cost[i] = min(cost[i], rec(i-j) + abs(h[i-j] - h[i]))
    done[i] = True
    return cost[i]

print(rec(N-1))