[Python] 백준 11049: 행렬 곱셈 순서

https://www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

1. ABCD 의 행렬이 주어졌을경우 행렬은 A(BCD), (AB)(CD), (ABC)D 총 4가지 경우의 수가 나오고 A(BCD)의 경우 BCD = B(CD), (BC)D 로 다시 쪼개진다.

2. 행렬은 r * c 이므로 각 행렬의 항을 a항에 넣어주면 점화식은

dy[s][e] = dy[s][k] + dy[k][e] + a[s]*a[k]*a[e]  (s+1 <=k <e)

3. 행렬의 곱은 행렬이 2개이상일때부터 성립함으로 (e-s >= 2) 이다

INF = 2**31
n = int(input())
dy = [[INF for _ in range(n+1)] for _ in range(n+1)]
a = [0 for _ in range(n+1)]

def dfs(s, e):
    if e-s <= 1:
        return 0
    if dy[s][e] != INF:
        return dy[s][e]
    for k in range(s+1, e):
        dy[s][e] = min(dy[s][e], dfs(s, k)+dfs(k, e)+a[s]*a[k]*a[e])
    return dy[s][e]

for i in range(n):
    a[i], a[i+1] = map(int, input().split())
    dy[i][i], dy[i][i+1] = 0, a[i]*a[i+1]

dfs(0, n)
print(dy[0][n])