Python 代码

n = int(input())
nums = list(map(int, input().split()))

dp = [[float('inf')] * (n+1) for _ in range(n+1)]

for length in range(1, n):
    for l in range(n-length):
        r = l + length
        if length == 1:
            dp[l][r] = 0
            continue
        if length == 2: 
            dp[l][r] = nums[l] * nums[r] * nums[l+1]
            continue
        for k in range(l+1, r):
            dp[l][r] = min(dp[l][r], dp[l][k] + dp[k][r] + nums[l] * nums[r] * nums[k])
print(dp[0][n-1])