• 동적 계획법의 유명한 문제인 연쇄 행렬 곱셈문제이다.
• O(nlogn) 알고리즘이 최적으로 알려져 있지만, 여기에서는 교과서에서 알려주는 O(n^3) 알고리즘으로 풀었다.
• 추후에 O(nlogn) 알고리즘을 구현해보고 업데이트 예정.
• BOJ의 행렬 곱셈 순서도 동일한 문제이지만, n<500 이라서 코드를 조금 더 최적화시켜야 통과 가능하다.

"""Solution code for "Programmers 12942. 최적의 행렬 곱셈".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/12942
- Solution link: http://www.teferi.net/ps/problems/programmers/12942
"""


def solution(matrix_sizes):
    n = len(matrix_sizes)
    dp = [[0] * n for _ in range(n)]
    for l in range(1, n):
        for i in range(n - l):
            j = i + l
            dp[i][j] = min(
                dp[i][k] + dp[k + 1][j] +
                matrix_sizes[i][0] * matrix_sizes[k][1] * matrix_sizes[j][1]
                for k in range(i, j))

    return dp[0][-1]