http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4663385
- 行列の順番は変えずに「どの区間の行列から掛け算するのが最善か」という問題
- 初期値は rep(i, 0, n) dp[i][i] = 0; それ以外は inf
- 繰り返しは rep(range, 1, n) rep(l, 0, n)
- 更新は rep(m, l, r) dp[l][r] = min(dp[l][r], dp[l][m] + dp[m+1][r] + nyaa[l] * nyaa[m+1] * nyaa[r+1]);
- 出力は dp[0][n-1]
- 区間DPの二重ループは range から書かないと答えが出ない
行列サイズ (p0, p1) と (p1, p2) の積は p0 × p1 × p2 だけ演算回数が必要。不思議なことに、どのグループから掛け算するかで演算回数が変化する（行列の順番は変えてはいけない）。
行列の行サイズを
、列サイズを
とする（列サイズのインデックスが1ずれることに注意）。閉区間で連続した2グループの行列積を考えると [l, m]×[m+1, r] となるので（l, m, r は p のインデックスに対応）、行列積は区間DPを使って以下のように計算する。
rep(m, l, r) dp[l][r] = min(dp[l][r], dp[l][m] + dp[m+1][r] + nyaa[l] * nyaa[m+1] * nyaa[r+1]);
