動的計画法 | アルゴリズム [AOJ 0557][Ruby][Python]

今回は、『AOJ 0557 - 動的計画法』についての記事です。

動的計画法(Dynamic Programming, DP)は、ベーシックなアルゴリズムのひとつです。動的計画法は次の条件を満たす必要があります。

分割統治法:部分問題を解き、その結果を利用して、問題全体を解く
メモ化:部分問題の計算結果を再利用する 

😎 Rubyコード

n = gets.to_i
arr = gets.split(' ').map(&:to_i)
answer = arr[n-1]
dp = n.times.map { [0]*21 }
dp[0][arr[0]] = 1
1.upto(n-2) do |i|
0.upto(20) do |j|
next if dp[i-1][j] <= 0
cp = j + arr[i]
cm = j - arr[i]
dp[i][cp] += dp[i-1][j] if cp <= 20
dp[i][cm] += dp[i-1][j] if cm >= 0
end
end
puts dp[n-2][answer]

🐠 Pythonコード

n = input()
arr = map(int, raw_input().split())
answer = arr[n-1]
dp = [[0]*21 for i in range(n)]
dp[0][arr[0]] = 1
for i in range(1, n-1):
for j in range(21):
if dp[i-1][j] == 0: continue
vp = j + arr[i]
vm = j - arr[i]
if vp <= 20:
dp[i][vp] += dp[i-1][j]
if vm >= 0:
dp[i][vm] += dp[i-1][j]
print dp[n-2][answer]

シンプルですがかなり強力なアルゴリズムなので知っておいて損はないと思います。ぜひトライしてみてください!

🐮 GitHubリポジトリ

当面はAOJを解きながら、アルゴリズムの再勉強をしていくつもりです。Ruby/PythonでのAOJの回答は下のリポジトリに保存しておきます。もしツッコミとかあればぜひ^^

morizyun/aoj-ruby-python - GitHub

📚 おすすめの書籍

💩 欲しいものリスト公開しました