動的計画法の例題です。連鎖行列積をやります。アルゴリズムの勉強と実装をします。

連鎖行列積

厳しい名前がついていますが、やることは行列の積の計算順序の決定です。与えられたn個の行列の連鎖 $M_1, M_2, \dots , M_n$ の積を計算しますが、計算結果には興味がありません。見つけたいのは、計算回数を最小にする積の順序です。

$l \times m$ 行列と $m \times n$ 行列の積では、 $l \times m \times n$ 回が計算が生じます。

例えば、 $M_1, M_2, M_2$ が与えられたとき、 $(M_1 M_2) M_2$ と $M_1 (M_2 M_3)$ のどちらが計算量が少ないか、ということです。

アルゴリズム

$M_i$ を $p_{i-1} \times p_i$ 行列とします。 $M_i M_{i+1}$ の計算回数は $p_{i-1} p_i p_{i+1}$ となります。計算回数をコストと呼ぶことにすると、上の例では、

$cost [ M_1 M_2 M_3 ] = min \{ cost [ (M_1 M_2) (M_3) ], cost [ (M_1)(M_2 M_3) ] \}$

ここで、

$cost [ (M_1 M_2) (M_3) ] = cost [M_1 M_2 ] + cost [M_3 ] + p_0 p_2 p_3$

$cost [ (M_1)(M_2 M_3) ] = cost [M_1 ] + cost [M_2 M_3 ] + p_0 p_1 p_3$

当然、 $1 \leq i \leq n$ について $cost [M_i ] = 0$ が成り立ちます。これを一般化すると、

$cost (i, j) = \left \{ \begin{array}{} 0 && (i = j) \\ min_{i \leq k \leq j - 1} \left \{ cost(i, k) + cost(k+1, j) + p_{i-1} p_k p_j \right \} && (i \neq j) \\ \end{array} \right.$

となります。ただし、 $M_i , \dots , M_j$ の最小コストを $cost(i, j)$ と書いています。

実装

次の問題を解いてみました。

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

ループの範囲に注意します。

解答例：

#include<iostream>
using namespace std;

#define N 100

int main() {
  int i, j, k, l, n, p[N+1], cost[N+1][N+1], min_cost;

  cin >> n;
  for (i = 1; i <= n; i++) cin >> p[i-1] >> p[i];

  // 初期値
  for (i = 1; i <= n; i++) cost[i][i] = 0;

  for (l = 2; l <= n; l++) {  // 行列の個数
    for (i = 1; i <= n - l + 1; i++) {
      j = i + l - 1;
      for (k = i; k < j; k++) {
        if (k == i) min_cost = cost[i][k] + cost[k+1][j] + p[i-1] * p[k] * p[j];
        else min_cost = min(min_cost, cost[i][k] + cost[k+1][j] + p[i-1] * p[k] * p[j]);
      }
      cost[i][j] = min_cost;
    }
  }

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

  return 0;
}