行列の鎖の最小の乗算回数

$A_i$ を $p_{i-1}\times p_i$ 行列（$i=1,\ldots,n$。$p_0,\ldots,p_n$ は正の整数）とする。$A_i\cdots A_j$（$i\le j$）の括弧づけを、$i=j$ のときは $A_i$ そのもの、$i\lt j$ のときはある $k$（$i\le k\lt j$）と $A_i\cdots A_k$ の括弧づけ $\mathcal{L}$、$A_{k+1}\cdots A_j$ の括弧づけ $\mathcal{R}$ の組 $(\mathcal{L}\,\mathcal{R})$ と再帰的に定め、その費用を

と定める。$A_i\cdots A_j$ の括弧づけの費用の最小値を $m(i,j)$ とする。

1. $m(i,i)=0$ であり、$i\lt j$ のとき $$m(i,j)=\min_{i\le k\lt j}\bigl\{m(i,k)+m(k+1,j)+p_{i-1}p_kp_j\bigr\}.$$
2. すべての $m(i,j)$ と、費用 $m(1,n)$ を達成する括弧づけは、$O(n^3)$ 時間・$O(n^2)$ 領域で求まる。