행렬 곱셈 문제
n개의 행렬 곱셈을 최소 비용으로 푸는 문제
만약 무지성으로 pXq , qXr 인 두 행렬을 3개 for루프로 풀면, O(pqr)번 연산이 필요하다.
이때 여러개의 행렬이 주어졌을 때는, 행렬을 어느 순서로 곱하느냐에 따라 기본 연산 횟수가 달라진다.
a = 1x2, b=2x3, c=3x4 일때, (ab)c와 a(bc)의 차이는 1x2x3x1x3x4 vs 1x2x4x2x3x4 의 차이다.
그렇다면 어떤 곱셈을 먼저 해야 최소 비용으로 행렬의 곱셈을 구할 수 있을까?
우리는 다이나믹 프로그래밍으로 풀어보자.
먼저 해의 성질은 분석해보자
n개의 행렬이 있다고 했을 때,
n개 곱셈비용은 어떤 행렬 i를 기점으로 곱셈 형식으로 된다.
즉 (M1 x…x Mi) X (M(i+1) x…x Mn) 이런 식이 될 것이다.
그렇다면? 결국 Mn = pn x qn 이라고 했을때
행렬의 곱셈 원칙에 따라, M1=p1 x p2, M2=p2 x p3… 이런 식이 되고,
{p1 x p(i+1)} x {p(i+1) x p(n+1)} 인 꼴이 된다.
점화식을 구현해보자
즉 M1 ~ Mn까지 최소 비용 = M1 ~ Mi 최소비용 + M(i+1) ~ Mn까지 최소비용 + 이 둘을 곱하는 비용{=p1 * p(i+1) * p(n+1)}
T(1,n) = T(1,i)+T(i+1, n)+둘 곱하는 비용
뭔가 점화식처럼 생겼다! 하지만 우리는 i가 어떤 수인지 모른다..
dp테이블을 구현해보자
그려면 dp테이블을 사용해서 다 해보자!
T에 두가지 수가 필요하므로, dp를 2차원 배열로 하여..
dp[1][n] = min(dp[1][i]+dp[i+1][n]+p1 * p(i+1) * p(n+1))으로 해서
i=1~n-1까지 대입해서 이 중 최소값을 찾으면 된다!!