# Matrix Chain

• 2026년 7월 31일 알고리즘
  추가 설명 — 어떤 순서로 곱했는지 되짚기

  동적 계획법 ③의 표는 최소 비용만 담는다. 어떤 괄호 순서로 곱해야 그 비용이 나오는지는 표에 없다. 채우는 동안 이긴 분할점 k를 함께 적어 두면 (1,n)에서 재귀로 (M₁(M₂M₃)) 같은 괄호화를 복원한다. d=[3,2,4,2] 예시로 되짚고, 파스 트리와 동점의 미묘함까지 짚는다.

• 2026년 7월 30일 알고리즘
  동적 계획법 ③ — 구간을 어디서 자를 것인가

  행렬 M₁×…×Mₙ을 곱할 때 결과는 같아도 곱셈 횟수는 괄호를 어디에 치느냐로 달라진다. (3×2)(2×4)(4×2)는 48번 대 28번. '이 구간의 마지막 곱을 어디서 하는가'라는 결정에서 M[i,j]=minₖ(M[i,k]+M[k+1,j]+d_{i-1}d_k d_j)를 세우고, 짧은 구간부터 채워 O(n³)에 푼다. dp-2의 결정 사고를 원소에서 구간으로 확장한다.