import sys
input = sys.stdin.readline
INF = 10**12
N = int(input())
matrix = []
for i in range(N):
matrix.append([*map(int,input().split())])
DP = [[INF]*N for i in range(N)]
for i in range(N):
DP[i][i] = 0
for k in range(1,N):
for i in range(N-k):
for j in range(i,i+k):
DP[i][i+k] = min(DP[i][i+k],DP[i][j]+DP[j+1][i+k]+matrix[i][0]*matrix[j][1]*matrix[i+k][1])
print(DP[0][N-1])
대략 한달이 넘도록 풀지 못했던 문제.
DP에서 구간의 크기를 변수로 생각해야 한다는걸 떠올리기가 정말 어려웠다.
알고리즘을 요약하면,
1. DP[i][j]는 i번째 행렬부터 j번째 행렬까지 곱셈을 했을때의 최솟값을 의미한다.
2. DP[i][i] = 0, 나머지는 INF로 설정한다.
3. 3중 for문을 돌린다. 이때 k는 구간의 크기, i는 시작위치, j는 중심을 의미한다.
4. i~j까지 곱했을 때의 행렬과 j~i+k까지 곱했을 때의 행렬, 두 행렬을 곱할 때의 횟수 + i~j를 곱할때 횟수 + j~i+k를 곱할때 횟수의 최솟값을 구해준다.
5. 0~N-1까지의 행렬을 모두 곱했을 때의 최솟값 (DP[0][N-1]) 을 출력한다.
오늘의 교훈) DP 응용 문제를 열심히 해야겠다