연쇄 행렬 곱셈 (Matrix-chain Multiplication) i × j 행렬과 j × k행렬을 곱하기 위해서는 일반적으로 i × j × k번 만큼의 기본적인 곱셈이 필요하다. 연쇄적으로 행렬을 곱할 때, 어떤 행렬곱셈을 먼저 수행하느냐에 따라서 필요한 기본적인 곱셈의 횟수가 달라지게 된다. 예를 들어서, 다음 연쇄행렬곱셈을 생각해 보자: A1 × A2 × A3 A1의 크기는 10 × 100이고, A2의 크기는 100 × 5이고, A3의 크기는 5 × 50라고하자. A1 × A2를 먼저 계산한다면, 기본적인 곱셈의 총 횟수는 7,500회 A2 × A3를 먼저 계산한다면, 기본적인 곱셈의 총 횟수는 75,000회 따라서, 연쇄적으로 행렬을 곱할 때 기본적인 곱셈의 횟수가 가장 적게 되는 최적의 순서..
