최적의 행렬 곱셈

def numop(r1, c1, r2, c2): return r1 * c1 * c2 def solution(matrix_sizes): M = matrix_sizes n = len(M) A = [[0] * n for _ in range(n)] # DP matrix의 i < j인 부분만 값을 채우는데, # d = j-i 의 값이 1, 2, ..., n-1 인 쌍의 순서대로 # 값을 채웁니다. for d in range(1, n): for i in range(n): j = i + d if j >= n: break if d == 1: A[i][j] = numop(M[i][0], M[i][1], M[j][0], M[j][1]) else: candidates = [] for k in range(d): # (1) i~i+k번째 행렬까지 최적으로 곱할 때의 연산 수와, a = A[i][i+k] # (2) i+k+1~j번째 행렬까지 최적으로 곱할 떄의 연산 수와, b = A[i+k+1][j] # (3) (i~i+k)번째 행렬곱과 (i+k+1~j)번째 행렬곱의 연산 수를 c = numop(M[i][0], M[i+k][1], M[i+k+1][0], M[j][1]) # 더한 값들을 비교해야 합니다. 후보 리스트에 넣고 최솟값을 구합시다. candidates.append(a+b+c) # A[i][j] 는 후보 리스트 중 최솟값입니다. A[i][j] = min(candidates) return A[0][n-1]