다이나믹 프로그래밍 적용 문제 (3) 행렬 곱셈 순서 문제 설명 행렬 A1, A2, A3, . . . , An을 곱하는 수를 최소로 하는 최적의 곱셈 순서를 구하라. 예로, 행렬 A(2 × 3), B(3 × 5), C(5 × 2)가 있을 때 곱할 수 있는 경우의 수는 다음과 같다. (AB)C = 2 × 3 × 5 + 2 × 5 × 2 = 50 A(BC) = 3 × 5 × 2 + 2 × 3 × 2 = 42 두 경우의 수에서 최솟값인 42에 해당하는 연산이 최소의 곱셈 횟수 42와 최적의 곱셈 순서 A(BC) 가 된다. 마지막 행렬 곱셈이 수행되는 상황을 다음과 같이 정리할 수 있으며, 경우의 수는 총 n - 1이다. 점화식 Ak의 크기 : pk-1 * pk m[i, j] : 행렬 Ai, …, Aj의 곱을 ..