区間DP
連鎖行列積
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])