동적 계획 의 매트릭스 연결 최적화 문제

1. 문제 설명
입력:, 그 중 Ai 는 pi - 1 * pi 매트릭스
출력: A1 * A2 *... * An 의 최소 대가 계산 방법
2. 알고리즘 분석
m (i, j) 가 ai ~ j 의 최소 곱셈 수 를 계산한다 고 가정 하면 m (i, j) 는 min (m (i, k) + m (k + 1, j) + pi - 1 * pk * pj) 와 같 기 때문에 i = j 일 때 m (i, j) = 0 이 있다.
초기 화 문제: 대각선 에 있 는 요소 m (i, i) 를 0 으로 설정 한 다음 대각선 을 따라 푸 시 구 조 를 전달 합 니 다.
3. 코드 구현

import numpy as np

#        
matrix = np.array([[2,3],[3,5],[5,3],[3,2],[2,6]])

#           
num = len(matrix)

#          
mlti_order = np.zeros(num*num).reshape(num,-1)

#          ， k 
mlti_k = np.zeros(num*num).reshape(num,-1)

#         ，      K      
INF = 1000

#      
for r in range(num - 1): #            0，       num-1    ，
    i = 0
    j = r + 1
    while (i < num - r) & (j < num): #   r+1       m(i,j)  
        k=i
        mlti_order[i][j] = INF 
        while k < j: #   m(i,j)，   k  m(i,k)+m(k+1,j)+pi-1*pk*pj  
            value = mlti_order[i][k] + mlti_order[k+1][j] + matrix[i][0]*matrix[k][1]*matrix[j][1]
            if value < mlti_order[i][j]:
                mlti_order[i][j] = value
                mlti_k[i][j] = k #    K 
            k += 1
            
        i += 1
        j += 1


print '            :',mlti_order[0][num-1],
   
def printOrder(order, i, j):
    if i == j:
        print 'A',i+1,  
    else:
        print '(',
        k = int(order[i][j])
        printOrder(order, i, k)
        printOrder(order, k+1, j)
        print ')',

print ',     :',printOrder(mlti_k, 0, num-1)

4. 시간의 복잡성
- 대 가 를 계산 하 는 시간: (r, i, k) 3 층 순환, 각 층 에서 n - 1 단계 까지 O (n ^ 3)
- 구조 최 적 화 된 시간: O (n)
- 총 시간 복잡 도: O (n ^ 3)
5. 공간 복잡성
- 배열 mlti 사용order 와 mlti_k. 대 가 를 저장 하고 화해 합 니 다. O (n ^ 2)