[프로그래머스] 최적의 행렬 곱셈 (DP)

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

프로그래머스

 

분석

 

2023.04.04 - [백준/동적계획법] - [11049번] 행렬 곱셈 순서 (행렬 곱 연산 횟수의 최솟값 구하기, DP)

[11049번] 행렬 곱셈 순서 (행렬 곱 연산 횟수의 최솟값 구하기, DP)

 

 

풀이

import sys
answer = sys.maxsize 

def solution(matrix_sizes):
    
    n= len(matrix_sizes)
    matrix_sizes.insert(0, (0,0))
    
    # 최소 연산 횟수 저장 리스트
    d=[[-1 for j in range(n+1)] for i in range(n+1)]

    def execute(s,e):
        answer = sys.maxsize 

        if d[s][e] != -1: # 이미 계산
            return d[s][e]
        
        if s==e: # 행렬 1개
            return 0
        
        if s+1==e: # 행렬 2개
            return matrix_sizes[s][0] * matrix_sizes[s][1] * matrix_sizes[e][1]

        for i in range(s,e):
            answer=min(answer, matrix_sizes[s][0] * matrix_sizes[i][1] * matrix_sizes[e][1] + execute(s,i) + execute(i+1,e))
            
        d[s][e]=answer
        return d[s][e]

    return execute(1,n)