python 動的計画法 part1

Atcorder始めたけれどなかなかC問題解けるようにならないので

ここで学んだことをまとめていく。

Tasks - AtCoder Beginner Contest 204

D問題で動的計画法が使われてる。

動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集 - Qiita

わかりやすそうなサイト。

まずはA.カエルのお話

 #足場の数とそれぞれの高さを受け取る 
N = int(input())
H = list(map(int, input(). split()))
 #動的計画法 
 #DPテーブルを設定 
dp = [float('inf') for _ in range(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]))

ans = dp[-1]
print(ans)

ループで書くのは直感的で理解しやすい。

再帰関数を使うやり方はとても難しい。できる人すごいな。

import sys
sys.setrecursionlimit(1000000000)

n = int(input())
h = list(map(int, input(). split()))
dp = [0]*n
check = [False]*n

def cost(i):
   if check[i]:
       return dp[i]
   else:
       #初期設定
       if i == 0:
           dp[i] = 0
       #i-1,i-2
       elif i == 1:
           dp[i] = abs(h[1] - h[0])
       elif i > 1:
           dp[i] = min(cost(i-1) + abs(h[i] - h[i-1]), cost(i-2) + abs(h[i] - h[i-2]))
       check[i] = True
       return dp[i]

print(cost(n-1))

どうやら再帰の数が多いとエラーが発生するらしい。それを抑えるのが最初の二行。

まとめ

動的計画法の基礎を学んだ。