区間DP（行列連鎖積）
DPテーブルが対角線から外側へ斜めに埋まる様子をステップ表示し、分割点 k で括弧の付け方と乗算回数が変わるのを体感します dp[i][j] = min(dp[i][k] + dp[k+1][j] + p·q·r)
4
各行列のサイズ列（次元 p₀,p₁,…,pₙ）を編集
表示する分割点 k（区間 [1, n] の最上位の分割）
k = 2
最小乗算回数 dp[1][n]
—
埋めた対角線（区間長）
—
選んだ分割 k のコスト
—
最適な括弧付け
DPテーブル dp[i][j]（対角線から外へ斜めに充填）
区間DPは「区間
短い区間ほど先に答えが決まるので、DPテーブルは対角線（区間長 1）から外側へ斜めに埋まっていきます。
行列連鎖積では
[i, j] の最適解」を、より短い区間の最適解から組み立てる手法です。
区間を分割点 k で [i, k] と [k+1, j] の2つに割り、その左右の最適コストを足し合わせて、もっとも安い k を選びます。短い区間ほど先に答えが決まるので、DPテーブルは対角線（区間長 1）から外側へ斜めに埋まっていきます。
行列連鎖積では
Aᵢ…Aⱼ の積の乗算回数を最小化し、回文分割では文字列をすべて回文に切る最小カット数を求めます。スライダーやボタンで動かしてみましょう。
いま何が起きている？
ここがポイント
- 小さい区間から先に解く ── 対角線（長さ1）が基底で、外側の長い区間へ斜めに埋める。
- 分割点 k で部分問題に分解 ──
dp[i][j] = min_k( dp[i][k] + dp[k+1][j] + 結合コスト )。 - 結合コストはモデル依存 ── 行列連鎖は
pᵢ₋₁·pₖ·pⱼ回の乗算、回文分割は分割なら +1 カット。 - 計算量 O(n³) ── 区間 O(n²) × 分割点 O(n)。最適な k を記録すれば括弧付け（分割）を復元できる。