【ALDS1_10】B: Dynamic Programming - Matrix Chain Multiplication
問題
連鎖行列積 | アルゴリズムとデータ構造 | Aizu Online Judge
方針
行列が5個与えられた時, 計算の順序は1.
2.
3.
など様々な順序がある. すべてのパターンを試すアルゴリズムでは, となってしまうため, これよりも計算効率の良いアルゴリズムを考える必要がある. 結果からいうと, この問題は動的計画法を用いることで効率よく計算することができる.
まずはじめに, 2つの行列の演算について考える. の演算方法は1通りであり, 行列 の行と列をそれぞれとしたとき, 演算回数は回となる. これらの結果はdpテーブルにメモしておく.
次に, の計算を考える. の計算では, との二通りが存在し, それらの小さいほうが最適解となる. このとき, やは事前に計算済みであることから, 改めて計算する必要はない.
以上より, 以下のような式を実装することで最適解を得ることができる.
コード
#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; }