algorithm - 行列の乗算

Question

動的計画法に関するコーメンのアルゴリズム入門を読んでいました。

行列の乗算を実行するには、行列の順序が重要です。多数の行列を乗算して最良の結果が得られた場合、系列に行列を追加してその結果を最適に保つにはどうすればよいですか?

Answer 1

あなたが持っている場合：

DP[i, j] = minimum cost of multiplying matrices i to through j

それからDP[1, n]あなたの答えになります。

を見つけるDP[1, n + 1]には、テーブルの作成に使用したのと同じ繰り返しを適用するだけです。

DP[1, n + 1] = min   {DP[1, k] + DP[k + 1, n + 1] + multiplication cost}
            1<=k<n+1

これは になりますO(n)。