pypy3(pypy3.6.1) 解法, 执行用时: 88ms, 内存消耗: 20688K, 提交时间: 2020-06-02 20:19:53

n=int(input())
a=list(map(int,input().split()))
dp=[[0 for i in range(n+10)]for i in range(n+10)]
for len in range(3,n+1):
    for l in range(n-len+1):
        r=l+len-1
        dp[l][r]=10**100
        for k in range(l+1,r):
            dp[l][r]=min(dp[l][r],dp[l][k]+dp[k][r]+a[l]*a[r]*a[k])
print(dp[0][n-1])

Python3(3.5.2) 解法, 执行用时: 68ms, 内存消耗: 3440K, 提交时间: 2020-06-03 10:44:58

n = int(input())
a = list(map(int, input().split()))
d = [([int(1e30)] * (n+1)) for i in range(n+1)]
for l in range(1, n):
	for i in range(0, n-l):
		j = i+l
		if(j-i == 1):
			d[i][j] = 0
			continue
		for k in range(i+1, j):
			d[i][j] = min(d[i][j], d[i][k] + d[k][j] + a[i]*a[j]*a[k])
print(d[0][n-1])