動的計画法 | アルゴリズム [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);
  }
}