酒と泪とRubyとRailsと

Ruby on Rails と Objective-C は酒の肴です!

アルゴリズムの勉強: 動的計画法[AOJ 0557][Ruby][Python]

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

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

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

Ruby サンプルソース

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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 サンプルソース

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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]

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

Aizu Online Judgeのサンプルソース

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

morizyun/aoj-ruby-python - GitHub

最近解いたAOJの問題

AOJタグのついた最近解いた問題一覧

おすすめの書籍