区間DP

連鎖行列積

AOJ

import sys
input = sys.stdin.buffer.readline
N = int(input())
*A, = map(int, sys.stdin.buffer.read().split())
A = [A[0]] + A[1::2]
INF = 1 << 30
dp = [[INF]*N for _ in [0]*N] # [l, r]まで積を取ったときの最小乗算回数

for i in range(N):
    dp[i][i] = 0

for length in range(1, N):  # 区間を徐々に広げていく
    for l in range(N-length):
        r = l + length
        for i in range(l, r): # [l,i]と[i,r]を結合する
            d = dp[l][i] + dp[i+1][r] + A[l]*A[i+1]*A[r+1]
            if dp[l][r] > d:
                dp[l][r] = d

print(dp[0][-1])