Problem:
 Score : 100 points    Problem Statement There are N slimes lining up in a row.
Initially, the i -th slime from the left has a size of a_i .  Taro is trying to combine all the slimes into a larger slime.
He will perform the following operation repeatedly until there is only one slime:   Choose two adjacent slimes, and combine them into a new slime. The new slime has a size of x + y , where x and y are the sizes of the slimes before combining them. Here, a cost of x + y is incurred. The positional relationship of the slimes does not change while combining slimes.   Find the minimum possible total cost incurred.      Constraints  All values in input are integers.  2 \leq N \leq 400  1 \leq a_i \leq 10^9         Input Input is given from Standard Input in the following format:  N  a_1  a_2  \ldots  a_N       Output Print the minimum possible total cost incurred.        Sample Input 1 4
10 20 30 40      Sample Output 1 190  Taro should do as follows (slimes being combined are shown in bold):   ( 10 , 20 , 30, 40) → ( 30 , 30, 40)  ( 30 , 30 , 40) → ( 60 , 40)  ( 60 , 40 ) → ( 100 )        Sample Input 2 5
10 10 10 10 10      Sample Output 2 120  Taro should do, for example, as follows:   ( 10 , 10 , 10, 10, 10) → ( 20 , 10, 10, 10)  (20, 10 , 10 , 10) → (20, 20 , 10)  (20, 20 , 10 ) → (20, 30 )  ( 20 , 30 ) → ( 50 )        Sample Input 3 3
1000000000 1000000000 1000000000      Sample Output 3 5000000000  The answer may not fit into a 32-bit integer type.       Sample Input 4 6
7 6 8 6 1 1      Sample Output 4 68  Taro should do, for example, as follows:   (7, 6, 8, 6, 1 , 1 ) → (7, 6, 8, 6, 2 )  (7, 6, 8, 6 , 2 ) → (7, 6, 8, 8 )  ( 7 , 6 , 8, 8) → ( 13 , 8, 8)  (13, 8 , 8 ) → (13, 16 )  ( 13 , 16 ) → ( 29 )

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()
    l = n + 1

    t = [[0]*n for _ in range(n)]
    w = [0] * l
    for i in range(n):
        w[i+1] = w[i] + a[i]

    for i in range(n-2,-1,-1):
        z = t[i]
        y = t[i+1]
        c = w[i]
        for j in range(i+1,n):
            b = inf
            for k in range(i,j):
                e = z[k] + t[k+1][j]
                if b > e:
                    b = e
            t[i][j] = b + w[j+1] - c

    return t[0][-1]


print(main())

Solution (Python):
from itertools import accumulate

n = int(input())
acc = [0] + list(accumulate(map(int, input().split())))
dp = [[0] * (n + 1) for _ in range(n)]
for w in range(2, n + 1):
    for l in range(n - w + 1):
        r = l + w
        dp[l][r] = min(dp[l][m] + dp[m][r] for m in range(l + 1, r)) + acc[r] - acc[l]
print(dp[0][n])

Solution (Python):
from itertools import accumulate

n = int(input())
aaa = list(map(int, input().split()))
acc = [0] + list(accumulate(aaa))
dp = [[0] * (n + 1) for _ in range(n)]
for l, aa in enumerate(zip(aaa, aaa[1:])):
    dp[l][l + 2] = sum(aa)
for w in range(3, n + 1):
    for l in range(n - w + 1):
        r = l + w
        dp[l][r] = min(dp[l][m] + dp[m][r] for m in range(l + 1, r)) + acc[r] - acc[l]
print(dp[0][n])

Solution (Python):
from itertools import accumulate

n = int(input())
aaa = list(map(int, input().split()))
acc = [0] + list(accumulate(aaa))
dp = [[0] * (n + 1) for _ in range(n)]
for l, aa in enumerate(zip(aaa, aaa[1:])):
    dp[l][l + 2] = sum(aa)
for w in range(3, n + 1):
    for l in range(n - w + 1):
        r = l + w
        c = acc[r] - acc[l]
        dp[l][r] = min(dp[l][m] + dp[m][r] + c for m in range(l + 1, r))
print(dp[0][n])

Solution (Python):
N=int(input())
A=list(map(int,input().split()))

DPLIST=[[None]*N for i in range(N)]

SUM=[0]
for i in range(N):
    DPLIST[i][i]=0
    SUM.append(SUM[-1]+A[i])

for i in range(1,N):
    for j in range(i,N):

        ANS=float("inf")

        for k in range(j-i,j):

            if ANS>DPLIST[j-i][k]+DPLIST[k+1][j]+SUM[j+1]-SUM[j-i]:
                ANS=DPLIST[j-i][k]+DPLIST[k+1][j]+SUM[j+1]-SUM[j-i]
        
        DPLIST[j-i][j]=ANS

print(DPLIST[0][N-1])

Solution (Python):
N=int(input())
A=list(map(int,input().split()))

DPLIST=[[None]*N for i in range(N)]

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

SUM=[0]
for i in range(N):
    SUM.append(SUM[-1]+A[i])

for i in range(1,N):
    for j in range(i,N):

        ANS=float("inf")

        for k in range(j-i,j):

            if ANS>DPLIST[j-i][k]+DPLIST[k+1][j]+SUM[j+1]-SUM[j-i]:
                ANS=DPLIST[j-i][k]+DPLIST[k+1][j]+SUM[j+1]-SUM[j-i]
        
        DPLIST[j-i][j]=ANS

print(DPLIST[0][N-1])

Solution (Python):
N=int(input())
A=list(map(int,input().split()))

DPLIST=[[None]*N for i in range(N)]

for i in range(N):
    DPLIST[i][i]=[0,A[i]]

for i in range(1,N):
    for j in range(i,N):
        
        ANS=float("inf")
        slime=float("inf")

        for k in range(j-i,j):
            sc1,sl1=DPLIST[j-i][k]
            sc2,sl2=DPLIST[k+1][j]

            if ANS>sc1+sc2+sl1+sl2:
                ANS=sc1+sc2+sl1+sl2
                slime=sl1+sl2
        
        DPLIST[j-i][j]=[ANS,slime]

    
    
            

print(DPLIST[0][N-1][0])

Solution (Python):
N = int(input())
*A, = map(int, input().split())

INF = 10**18
S = [0]*(N+1)
for i in range(N):
    S[i+1] = S[i] + A[i]
dp = [[0]*(N+1) for i in range(N+1)]
for k in range(2, N+1):
    for i in range(N-k+1):
        dp[i][k] = min(dp[i][j] + dp[i+j][k-j] for j in range(1, k)) + S[i+k] - S[i]
print(dp[0][N])

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
cost = [0]
for p in a:
	cost.append(cost[-1] + p)
def get_cost(l, r):
	return cost[r+1] - cost[l]

dp = [[float("inf") for _ in range(n)] for _ in range(n)]
for i, p in enumerate(a):
	dp[i][i] = 0

for g in range(1, n):
	for l in range(n-g):
		r = l + g
		for m in range(l, r):
			dp[l][r] = min(dp[l][r], dp[l][m] + dp[m+1][r] + get_cost(l, r))


print(dp[0][n-1])

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
cost = [0]
for p in a:
	cost.append(cost[-1] + p)
def get_cost(l, r):
	return cost[r+1] - cost[l]

dp = [[float("inf") for _ in range(n)] for _ in range(n)]
for i, p in enumerate(a):
	dp[i][i] = 0

for g in range(1, n):
	for l in range(n-g):
		r = l + g
		for m in range(l, r):
			dp[l][r] = min(dp[l][r], dp[l][m] + dp[m+1][r] + get_cost(l, r))


print(dp[0][n-1])

Solution (Python):
import sys
sys.setrecursionlimit(10**8)

N = int(input())
A = list(map(int,input().split()))
C = [0]
for a in A:
    C.append(C[-1] + a)

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

def rec(l,r):
    if dp[l][r]: return dp[l][r]
    if l == r: return 0
    if r-l == 1: return A[l] + A[r]
    ret = C[r+1] - C[l]
    tmp = min(rec(l+1,r), rec(l,r-1))
    for i in range(r-l-2):
        tmp = min(tmp, rec(l,l+i+1) + rec(l+i+2,r))
    ret += tmp
    dp[l][r] = ret
    return ret

print(rec(0,N-1))

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
dp = [[float("inf")] * (n+1) for i in range(n+1)]
rui = [0] * (n+1)
for i in range(n):
  rui[i+1] = rui[i] + a[i]
for i in range(n+1):
  for j in [-1,0,1]:
    if i + j > n:
      continue
    if i+j < 0:
      continue
    dp[i][i+j] = 0
for j in range(2,n+1):
  for i in range(n+1-j):
    for k in range(j):
      dp[i][i+j] = min(dp[i][i+k] +dp[i+k][i+j] + rui[i+j]-rui[i],dp[i][i+j])
print(dp[0][n])

Solution (Python):
from itertools import accumulate
N=int(input())
a=[int(i) for i in input().split()]
dp=[[float("inf")]*(N+1) for i in range(N+1)]
S=[0]+list(accumulate(a))
for i in range(N):
  dp[i][i+1]=0
for d in range(2,N+1):
  for i in range(N+1-d):
    for k in range(i+1,i+d):
      dp[i][i+d]=min(dp[i][i+d],dp[i][k]+dp[k][i+d]+S[i+d]-S[i])
print(dp[0][N])

Solution (Python):
from itertools import accumulate
n = int(input())
alst = list(map(int, input().split()))
acc = [0] + list(accumulate(alst))
dp = [[None] * (n + 1) for _ in range(n + 1)]
for i in range(n):
  dp[i][i] = 0

for length in range(2, n + 1):
  for left in range(n - length + 1):
    right = left + length - 1
    dp[left][right] = min([dp[left][k] + dp[k + 1][right] for k in range(left, right)]) + acc[right + 1] - acc[left]
print(dp[0][n - 1])

Solution (Python):
N=int(input())
A=[int(i) for i in input().split()]
dp=[[10**23]*N for i in range(N)]
S=[0]*(N+1)
for i in range(1,N+1):
    S[i]=S[i-1]+A[i-1]
for i in range(N):
    dp[i][i]=0
for k in range(1,N):
    for i in range(N-k):
        for l in range(i,i+k):
            dp[i][i+k]=min(dp[i][i+k],dp[i][l]+dp[l+1][i+k]+S[i+k+1]-S[i])
print(dp[0][N-1])

Solution (Python):
from itertools import accumulate

INF = float('inf')

N = int(input())
As = list(map(int, input().split()))

accAs = [0] + list(accumulate(As))

dp = [[0] * (N) for _ in range(N)]
for num in range(2, N+1):
    for i in range(N-num+1):
        cost = INF
        for j in range(1, num):
            cost = min(cost, dp[i][i+j-1] + dp[i+j][i+num-1])
        dp[i][i+num-1] = accAs[i+num] - accAs[i] + cost

print(dp[0][N-1])