Python 代码

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

s = [0] * (n+1)
for i in range(1, n+1): s[i] = s[i-1] + nums[i-1]

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

for k in range(n):
    for l in range(1, n-k+1):
        r = l + k
        if k == 0: dp[l][r] = 0
        else:
            for x in range(l, r):
                dp[l][r] = min(dp[l][r], dp[l][x] + dp[x+1][r] + s[r] - s[l-1])
print(dp[1][n])