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


今回は、『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]

🏀 Javaコード

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] tmp = br.readLine().split(" ");
int[] arr = Arrays.asList(tmp).stream().mapToInt(x -> Integer.parseInt(x)).toArray();
long[][] dp = new long[n][21];
dp[0][arr[0]] = 1;
for (int i = 1; i < n - 1; i++) {
for (int j = 0; j < 21; j++) {
if (dp[i-1][j] <= 0) {
continue;
}
if (j + arr[i] <= 20) {
dp[i][j + arr[i]] += dp[i-1][j];
}
if (j - arr[i] >= 0) {
dp[i][j - arr[i]] += dp[i-1][j];
}
}
}
int answer = arr[n-1];
long count = dp[n-2][answer];
System.out.println(count);
}
}

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

🚜 GitHubリポジトリ

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

morizyun/aoj-ruby-python - GitHub

📚 おすすめの書籍

🖥 サーバについて

このブログでは「Cloud Garage」さんのDev Assist Program(開発者向けインスタンス無償提供制度)でお借りしたサーバで技術検証しています。 Dev Assist Programは、開発者や開発コミュニティ、スタートアップ企業の方が1GBメモリのインスタンス3台を1年間無料で借りれる心強い制度です!(有償でも1,480円/月と格安)