日々精進

aikoと旅行とプログラミング

【ALDS1_10】B: Dynamic Programming - Matrix Chain Multiplication

問題

連鎖行列積 | アルゴリズムとデータ構造 | Aizu Online Judge

方針

行列が5個与えられた時, 計算の順序は

1.  {((((M_1 M_2) M_3) M_4) M_5)}
2.  {(M_1 (M_2 (M_3 (M_4 M_5))))}
3.  {( ( M_1 M_2 ) ( ( M_3 M_4)M_5))}

など様々な順序がある. すべてのパターンを試すアルゴリズムでは,  {O(n!)}となってしまうため, これよりも計算効率の良いアルゴリズムを考える必要がある. 結果からいうと, この問題は動的計画法を用いることで効率よく計算することができる.
 まずはじめに, 2つの行列の演算について考える.  M_{i-1}M{i} の演算方法は1通りであり, 行列  {M_i} の行と列をそれぞれ p\_{i-1}, p\_iとしたとき, 演算回数は p_{i-1} \times p_i \times p_{i+1}回となる. これらの結果はdpテーブルにメモしておく.
 次に,  (M_{0}M_{1}M_{2}), (M_{1}M_{2}M_{3}), (M_{2}M_{3}M_{4}) \cdots (M_{n-2}M_{n-1}M_{n}) の計算を考える.  (M_{0}M_{1}M_{2})の計算では,  ( (M_{0}M_{1})M_{2}) (M_{0}(M_{1}M_{2}) )の二通りが存在し, それらの小さいほうが最適解となる. このとき,  (M\_{0}M\_{1}) (M\_{1}M\_{2})は事前に計算済みであることから, 改めて計算する必要はない.
 以上より, 以下のような式を実装することで最適解を得ることができる.

 {\begin{equation} m[i][j] = \begin{cases} 0  & \text{(if i = j)} \\\min_{i \leq k \leq j} \{m[i][k] + m[k+1][j] + p[i-1] \times p[k] \times p[j] \}  & \text{(if i < j)} \end{cases} \end{equation}}


コード

#include <iostream>

using namespace std;

#define rep(i,n) REP(i,0,n)
#define REP(i,a,n) for(int i = a ; i < (int)n ; i++)

#define N 101

int dp[N+1][N+1], p[N+1];

int main(){
  int n;
    
  cin >> n;
  REP(i, 1, n+1){
    cin >> p[i-1] >> p[i];
  }
    
  REP(l, 2, n+1){           // 対象とする行列の数
    REP(i, 1, n-l+2){     
      int j = i + l - 1;   
      dp[i][j] = (1 << 20); // dp[i][j] := [Mi, Mj]の最小回数
      REP(k, i, j){
	dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j]);
      }
    }
  }

  cout << dp[1][n] << endl;

  return 0;
}