ABC004 Dを動的計画法で解きたい -> 動的計画法って何？ -> accoderに動的計画法のコンテストがある！ という順番です。
DPとはDynamic Programming、動的計画法の略です。
動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。
Wikipedia 動的計画法
動的計画法（Dynamic Programming）をサルでも分かるように説明する – その１（フィボナッチ数列）
問題
A – Frog 1
回答
Pythonで解いているという以外は、こちらの記事のほぼ写経です。
わかりやすくてとても素晴らしい記事でした。
まずは、状態を管理する配列 dp用意します。
配列のインデックスiがその時点を表し、dp[i]でその時点での状態を表します。
そして、数列の漸化式のような感じで、dpの値を前から順番に更新していくことで、最終的な回答に辿り着くことができます。
貰うDP
ノード i への遷移方法を考える。
過去の状態 dp[ i - 2 ] と dp[ i - 1 ]からその情報をもらうことで、現時点dp[ i ]の状態を考えます。
つまり、 dp[ i - 2 ] と dp[ i - 1 ] の値がわかっているときに、dp[ i ] の値を更新します。
n = int(input())
h = [int(i) for i in input().split()]
# dpの最小値を変更する関数
def chmin(a, b):
if a > b:
return b
else:
return a
# 無限大の値
f_inf = float('inf')
# DP テーブルを初期化 (最小化問題なので INF に初期化)
dp = [f_inf] * (10**5+10)
# 初期条件
dp[0] = 0
# 足場 i-1 から足場 i へ移動する。コストは|h[i]−h[i-1]|
# 足場 i-2 から足場 i へと移動する コストは |h[i]−h[i-2]|
for i in range(1, n):
dp[i] = chmin(dp[i], dp[i - 1] + abs(h[i] - h[i-1]))
# 一番目の足場では一つ前しか存在しない
if i > 1:
dp[i] = chmin(dp[i], dp[i - 2] + abs(h[i] - h[i -2]))
print(dp[n-1])
配るDP
ノード i からの遷移方法を考える。
現在の状態dp[ i ]の情報を未来に配るイメージで、未来の状態 dp[ i + 1 ] と dp[ i + 2 ] を予測します。
つまり、 dp[ i ] の値がわかっているときに、dp[ i + 1 ] と dp[ i + 2 ] の値を更新します。
n = int(input())
h = [int(i) for i in input().split()]
# dpの最小値を変更する関数
def chmin(a, b):
if a > b:
return b
else:
return a
# 無限大の値
f_inf = float('inf')
# DP テーブルを初期化 (最小化問題なので INF に初期化)
dp = [f_inf] * (10**5+10)
# 初期条件
dp[0] = 0
# 足場 i から足場 i+1 へ移動する。コストは|h[i]−h[i+1]|
# 足場 i から足場 i+2 へと移動する コストは |h[i]−h[i+2]|
for i in range(n-1):
dp[i + 1] = chmin(dp[i + 1], dp[i] + abs(h[i] - h[i + 1]))
# n-2の時は2つ先はない
if i < n-2:
dp[i + 2] = chmin(dp[i + 2], dp[i] + abs(h[i] - h[i + 2]))
print(dp[n-1])
メモ化再帰
DPの問題は、同じ分割統治の考え方で、再帰を使い解くことができます。
ここでは、すでに分かっている値をメモしておくことで計算時間を節約するメモ化再帰を使います。
import sys
sys.setrecursionlimit(10**5+10)
n = int(input())
h = [int(i) for i in input().split()]
# 無限大の値
f_inf = float('inf')
# メモ用のDP テーブルを初期化 (最小化問題なので INF に初期化)
dp = [f_inf] * (10**5+10)
# dpの最小値を変更する関数
def chmin(a, b):
if a > b:
return b
else:
return a
# メモ化再帰の関数
def rec(i):
# DPの値が更新されている場合はその値を返す
if dp[i] < f_inf:
return dp[i]
# 再帰の終了条件。足場0のコストは0
if i == 0:
return 0
# i-1, i-2 を再帰
res = f_inf
# i-1 から来た場合
res = chmin(res, rec(i-1) + abs(h[i] - h[i-1]))
# i-2 から来た場合
if i > 1:
res = chmin(res, rec(i-2) + abs(h[i] - h[i-2]))
# 結果をメモする
dp[i] = res
return res
ans = rec(n-1)
print(ans)
Pythonでの再帰処理の回数設定
メモ化再帰の回答をatcoderに最初に提出した時はエラーが出ました。
これは Pythonがデフォルトで許容する再帰処理の回数（1000回）を超えてしまったためと思われます。下記記事を参考に、最大の再帰処理回数を増やすことでエラーは出なくなりました。ただし、メモリの使用量が以前のDPと比較すると7倍ぐらいになってしまいました。