094 행렬 곱셈 순서 (미해결)

첫번째 코드

 

점화식 작성이 잘 이해가 되지 않았다.

그래서 책의 내용대로 DP의 개념을 다시 생각하면서 과정을 거쳤다.

 

코드는 책을 참고하여 작성하였지만, 시간초과가 나타나 해당 부분을 해결하지 못했다.

 

import sys
input = sys.stdin.readline

n = int(input())
D = [[-1 for _ in range(n+1)] for _ in range(n+1)]
m = []
m.append((0, 0))

for _ in range(n):
    x, y = map(int, input().split())
    m.append((x, y))

def execute(s, e):
    result = sys.maxsize
    if D[s][e] != -1:
        return D[s][e]
    if s == e:
        return 0
    if s+1 == e:
        return m[s][0] * m[s][1] * m[e][1]
    for i in range(s, e):
        result = min(result, m[s][0] * m[i][1] * m[e][1] + execute(s, i) + execute(i+1, e))
    D[s][e] = result
    return D[s][e]

print(execute(1, n))

 

시간초과

---

링크