matrix-chain Multiplication

행렬의 곱셈.

pxq 행렬 A와 qxr 행렬 B 곱하기.

void product(int A[][], int B[][], int C[][]) {
  for(int i = 0; i<p; i++) {
    for(int j = 0; j<r; j++) {
      C[i][j] = 0;
      for(int k=0; k<q; k++) {
        C[i][j] += A[i][k]*B[k][j];
      }
    }
  }
}

곱셈연산의 횟수 = pqr

Matrix 곱하기

Optimal Substructure

행렬의 곱셈을 문제를 적절한 순환식으로 표현하여, memoization or bottom up으로 풀어보자.

Optimal Substuructure인지 확인 하기

• 이 문제의 최적해가 이거다 라고 가정했을 때,

• 이 최적해의 일부분이 그 부분에 대한 최적해인지 확인하면된다.

뭔소린지 모르겠다..