동적 프로그래밍(dynamic programming) 방법으로 최소의 원소단위 곱셈 횟수를 갖도록 연쇄 행렬곱셈(matrix-chain multiplication)의 순서를 정하려 한다. c i , j c_{i,j} c i , j M i M_i M i M j M_j M j c i , j c_{i,j} c i , j i < j i \lt j i < j p 0 , p 1 , … , p n p_0, p_1, \ldots ,p_n p 0 , p 1 , … , p n M i M_i M i p i − 1 × p i p_{i-1} \times p_i p i − 1 × p i 1 c i , j = { 0 if i = j min i ≤ k ≤ j − 1 { c i , k + c k + 1 , j + p i − 1 p k p j } if i < j c_{i,j} = \begin{cases} 0 & \text{if } i = j \\ \min_{i \le k \le j-1}\{c_{i,k}+c_{k+1,j}+p_{i-1}p_kp_j\} & \text{if } i \lt j \end{cases} c i , j = { 0 min i ≤ k ≤ j − 1 { c i , k + c k + 1 , j + p i − 1 p k p j } if i = j if i < j 2 c i , j = { 0 if i = j min i ≤ k ≤ j − 1 { c i , k + c k , j + p i − 1 p k − 1 p j } if i < j c_{i,j} = \begin{cases} 0 & \text{if } i = j \\ \min_{i \le k \le j-1}\{c_{i,k}+c_{k,j}+p_{i-1}p_{k-1}p_j\} & \text{if } i \lt j \end{cases} c i , j = { 0 min i ≤ k ≤ j − 1 { c i , k + c k , j + p i − 1 p k − 1 p j } if i = j if i < j 3 c i , j = { 0 if i = j min i ≤ k ≤ j − 1 { c i , k − 1 + c k , j + p i − 1 p k − 1 p j } if i < j c_{i,j} = \begin{cases} 0 & \text{if } i = j \\ \min_{i \le k \le j-1}\{c_{i,k-1}+c_{k,j}+p_{i-1}p_{k-1}p_j\} & \text{if } i \lt j \end{cases} c i , j = { 0 min i ≤ k ≤ j − 1 { c i , k − 1 + c k , j + p i − 1 p k − 1 p j } if i = j if i < j 4 c i , j = { 0 if i = j min i ≤ k ≤ j − 1 { c i , k + c k , j + p i − 1 p k p j } if i < j c_{i,j} = \begin{cases} 0 & \text{if } i = j \\ \min_{i \le k \le j-1}\{c_{i,k}+c_{k,j}+p_{i-1}p_kp_j\} & \text{if } i \lt j \end{cases} c i , j = { 0 min i ≤ k ≤ j − 1 { c i , k + c k , j + p i − 1 p k p j } if i = j if i < j 해설
올바른 관계식은 c i , j = min i ≤ k ≤ j − 1 { c i , k + c k + 1 , j + p i − 1 p k p j } c_{i,j}=\min_{i \le k \le j-1}\{c_{i,k}+c_{k+1,j}+p_{i-1}p_kp_j\} c i , j = min i ≤ k ≤ j − 1 { c i , k + c k + 1 , j + p i − 1 p k p j }
분할점 k에서 M i ⋯ M k M_i \cdots M_k M i ⋯ M k M k + 1 ⋯ M j M_{k+1} \cdots M_j M k + 1 ⋯ M j p i − 1 × p k p_{i-1} \times p_k p i − 1 × p k p k × p j p_k \times p_j p k × p j p i − 1 p k p j p_{i-1}p_kp_j p i − 1 p k p j
c i , k + c k , j + p i − 1 p k − 1 p j c_{i,k}+c_{k,j}+p_{i-1}p_{k-1}p_j c i , k + c k , j + p i − 1 p k − 1 p j M k M_k M k c i , k − 1 + c k , j c_{i,k-1}+c_{k,j} c i , k − 1 + c k , j i ≤ k ≤ j − 1 i \le k \le j-1 i ≤ k ≤ j − 1 c i , i − 1 c_{i,i-1} c i , i − 1 c i , k + c k , j + p i − 1 p k p j c_{i,k}+c_{k,j}+p_{i-1}p_kp_j c i , k + c k , j + p i − 1 p k p j M k M_k M k 오류나 개정된 내용이 보이면 알려주세요