BEN2のブログ

たまに書いています。

AOJ ALDS1_10_B : Matrix Chain Multiplication

競技プログラミング

AOJ ALDS1_10_B : Matrix Chain Multiplication についてのメモを残します。

参考

区間 DP

螺旋本では、漸化式を立ててループ (非再帰) で計算する方法が説明されています。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N; cin >> N;
  vector<int> p(N+1);
  for (int i = 1; i <= N; i++) cin >> p.at(i-1) >> p.at(i);
  const int INF = 1000000007;
  // dp[i][j] := M_i M_i+1 ... M_j の掛け算の回数の最小値
  vector<vector<int>> dp(N+1, vector<int>(N+1, INF));
  for (int i = 1; i <= N; i++) dp.at(i).at(i) = 0;
  // 行列の個数 2 個, 3 個, ... と増やしていく
  for (int length = 2; length <= N; length++) {
    for (int i = 1; i <= N - length + 1; i++) {
      int j = i + length - 1;
      for (int k = i; k <= j-1; k++) {
        int tmp = p.at(i-1) * p.at(k) * p.at(j);
        // M_i ... M_k と M_k+1 ... M_j の掛け算の回数
        int cnt = dp.at(i).at(k) + dp.at(k+1).at(j) + tmp;
        dp.at(i).at(j) = min(dp.at(i).at(j), cnt);
      }
    }
  }
  cout << dp.at(1).at(N) << endl;
}

メモ化再帰

たとえば、連鎖行列積 M_{1} M_{2} M_{3} M_{4} の場合、

  • M_{1} と M_{2} M_{3} M_{4} の積
  • M_{1} M_{2} と M_{3} M_{4} の積
  • M_{1} M_{2} M_{3} と M_{4} の積

これらのうち、掛け算の回数が少ないものを採用する。

#include <bits/stdc++.h>
using namespace std;

const int INF = 1000000007;
vector<int> p;
vector<vector<int>> dp;

// func(i, j) := 積 M_i M_i+1 ... M_j の掛け算回数の最小値を返す
int func(int i, int j) {
  if (i == j) return dp.at(i).at(j) = 0;
  if (dp.at(i).at(j) != INF) return dp.at(i).at(j);
  int res = INF;
  for (int k = 0; k < j - i; k++) {
    int tmp = p.at(i-1) * p.at(i+k) * p.at(j);
    // M_i ... M_i+k と M_i+k+1 ... M_j の積
    int cnt = func(i, i+k) + func(i+k+1, j) + tmp;
    res = min(res, cnt);
  }
  return dp.at(i).at(j) = res;
}

int main() {
  int N; cin >> N;
  p.resize(N+1);
  for (int i = 1; i <= N; i++) cin >> p.at(i-1) >> p.at(i);
  dp = vector<vector<int>>(N+1, vector<int>(N+1, INF));
  cout << func(1, N) << endl;
}