##A - Frog 1

O(N)
受け取るDPが一番作りやすいです。

python

import sys
import math
import heapq
import itertools
from collections import deque
from functools import reduce

# main
def main():
    N = int(input())
    H = list(map(int, input().split()))

    dp = [1000000007] * (N)
    dp[0] = 0

    for i in range(1, N):
        dp[i] = min(dp[i], dp[i-1] + abs(H[i] - H[i-1]))
        if i>1:
            dp[i] = min(dp[i], dp[i-2] + abs(H[i] - H[i-2]))

    print(dp[N-1])
            
# エントリポイント
if __name__ == '__main__':
    main()

メモ化再帰

python

import sys
import math
import heapq
import itertools
from collections import deque
from functools import reduce

H = []
dp = []

def dfs(n)->int:
    global dp
    
    if n<0:
        return 0
    if dp[n]<1000000007:
        return dp[n]
    
    dp[n] = min(dp[n], dfs(n-1) + abs(H[n] - H[n-1]))
    if n>1:
        dp[n] = min(dp[n], dfs(n-2) + abs(H[n] - H[n-2]))

    return dp[n]


# main
def main():
    sys.setrecursionlimit(1000000)
    global H, dp
    
    N = int(input())
    H = list(map(int, input().split()))

    dp = [1000000007] * (N)
    dp[0] = 0

    dfs(N-1)

    print(dp[N-1])
            
# エントリポイント
if __name__ == '__main__':
    main()

##B - Frog 2

O(N)
受け取るDPが一番作りやすいです。
A - Frog 1の応用ですね。
任意のKまでDPを受け取ります。

python

import sys
import math
import heapq
import itertools
from collections import deque
from functools import reduce

# main
def main():
    N, K = list(map(int, input().split()))
    H = list(map(int, input().split()))

    dp = [1000000007] * (N)
    dp[0] = 0

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

    print(dp[N-1])
            
# エントリポイント
if __name__ == '__main__':
    main()

##H - ハードル走

O(N)

python

import sys
import math
import heapq
import itertools
from collections import deque
from functools import reduce

# main
def main():
    N, L = list(map(int, input().split()))
    X = list(map(int, input().split()))
    T = list(map(int, input().split()))

    hurdle = [False] * (L+1)
    for index in X:
        hurdle[index] = True

    dp = [1000000007] * (L+1)
    dp[0] = 0
    for i in range(1, L+1):
        dp[i] = min(dp[i], dp[i-1] + T[0])
        if i-2>=0:
            dp[i] = min(dp[i], dp[i-2] + T[0] + T[1])
        if i-4>=0:
            dp[i] = min(dp[i], dp[i-4] + T[0] + (T[1] * 3))
        if hurdle[i]:
            dp[i] += T[2]
    
    ans = dp[L]
    for i in [L-3, L-2, L-1]:
        if i>=0:
            ans = min(ans, dp[i] + T[0]//2 + T[1]*(2*(L-i)-1)//2)

    print(ans)
            
# エントリポイント
if __name__ == '__main__':
    main()