12月でDPをマスターする猫

はじめに

DPというアルゴリズムを一ヶ月でマスターする!

今回の問題

今日の問題
なんかカエルが飛ぶ問題です。
詳しくはリンク飛んでみてください。

猫:カエルが1個先に飛ぶのか2個先に飛ぶのかの２択をすべて考えて最小値を取れば解くことができるのだ。

猫が書いてる様子↓

import sys
sys.setrecursionlimit(1000000)#再帰の上限設定
n = int(input())
hlist = list(map(int,input().split()))

def dfs (a,score):
  if a == n-1:
    return score
  next_a1 = a+1
  next_a2 = a+2
  if next_a1 < n:
    newscore = score + abs(hlist[a]-hlist[next_a1])
    minimum = dfs(next_a1,newscore)
  if next_a2 < n:
    newscore = score + abs(hlist[a]-hlist[next_a2])
    minimum = min(minimum,dfs(next_a2,newscore))
  
  return minimum
print(dfs(0,0))

猫:あれ時間オーバーしてる(泣)

主:漸化式みたいに解くと早いよ

n = int(input())
hlist = list(map(int,input().split()))
dp = [1e10]*n#十分大きい値
dp[0] = 0
dp[1] = abs(hlist[1] - hlist[0])
for i in range(2,n):
  mae1 = dp[i-1] + abs(hlist[i] - hlist[i-1])
  mae2 = dp[i-2] + abs(hlist[i] - hlist[i-2])
  dp[i] = min(dp[i],mae1,mae2)
print(dp[n-1])

主:n番目の最小値を知るためにはn-1番目の最小値かn-2番目の最小値を見ると高速に求めることができるよ。

猫:理解