최적의 행렬 곱셈

https://programmers.co.kr/learn/courses/30/lessons/12942

• flow of the solution
  기본적으로 greedy 한 solution 없이 모든 matrix multiplication 경우를 확인해야 한다. 이는 answer(n) 을 구할때 answer(n-1) 경우를 n번 만큼 탐색하고 계산해봐야 하므로 최소 O(N^2) 의 시간복잡도를 가지게 된다. 풀이 자체는 visit[i][j] : 인덱스 i부터 j까지일때 matmul 최소값 을 recursive 하게 divide 혹은 dp처럼 구하면 된다. 효율성에서 중요한 점은 이 때, 중복된 연산을 체크하여 최소화하고 자료구조를 잘 선택해서 메모리 사용을 줄이는 것이 관건이다.

  for a in range(i, j):
      result = min(result, sol(i,a,visit,mat,Max)+sol(a+1,j,visit,mat,Max)+mat[i][0]*mat[a][1]*mat[j][1])
      

• result
  https://github.com/songjy6565/alg-py/blob/master/programmers/level4/A12945.py