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):
from itertools import accumulate
INF=1001001001001
n=int(input())
a=list(map(int,input().split()))
dp=[[INF for i in range(n+1)] for j in range(n+1)]
wa=[0]+list(accumulate(a))
for i in range(n):
  dp[i][i+1]=0
for gap in range(2,n+1):
  for l in range(n-gap+1):
    r=l+gap
    dp[l][r]=wa[r]-wa[l]+min(dp[l][k]+dp[k][r] for k in range(l+1,r))
print(dp[0][n])

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

DP = [[(0, float('inf'))] * (N+1) for _ in range(N)]

for num in range(1, N+1):
    for start in range(N):
        end = start + num
        if end > N:
            break
        if num == 1:
            DP[start][end] = (A[start], 0) 
            continue
        for i in range(start + 1, end):
            tmp = DP[start][i][0] + DP[start][i][1] + DP[i][end][0] + DP[i][end][1]
            large = DP[start][i][0] + DP[i][end][0]
            if DP[start][end][1] > tmp:
                DP[start][end] = (large, tmp)
print(DP[0][N][1])

Solution (Python):
import sys
from itertools import accumulate
import math

def main():
  input=sys.stdin.readline
  n=int(input())
  A=list(map(int,input().split()))
  dp=[[math.inf]*n for _ in range(n)]
  for i in range(n):
    dp[i][i]=0
  
  accA=list(accumulate([0]+A))
  
  for L in reversed(range(n)):
    dpL=dp[L]
    for R in range(L+1,n):
      dpL[R]=min([dpL[k-1]+dp[k][R] for k in range(L+1,R+1)])+accA[R+1]-accA[L]
  
  print(dp[0][-1])
main()

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

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

def f(l, r):
  if 0 < dp[l][r]:
    return dp[l][r]
  if l == r:
    return 0
  fans = float('inf')
  for m in range(r)[l:]:
    fans = min(fans, f(l, m)+f(m+1, r))
  dp[l][r] = fans + sum(A[l:r+1])
  return dp[l][r]
  
print(f(0,N-1))

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

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

def f(l, r):
  if 0 < dp[l][r]:
    return dp[l][r]
  if l == r:
    return 0
  fans = float('inf')
  for m in range(r)[l:]:
    fans = min(fans, f(l, m)+f(m+1, r))
  dp[l][r] = fans + sum(A[l:r+1])
  return dp[l][r]
  
print(f(0,N-1))

Solution (Python):
from itertools import accumulate

INF = 10**18

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

S = [0] + list(accumulate(A))

dp = [[INF for j in range(N + 1)] for i in range(N + 1)]

for i in range(N):
    dp[i][i + 1] = 0
    
for k in range(1, N + 1):
    for i in range(0, N - k + 1):
        for j in range(i, i + k + 1):
            dp[i][i + k] = min(dp[i][i + k], dp[i][j] + dp[j][i + k] + S[i + k] - S[i])

print(dp[0][N])

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
flag=[[0 for j in range(n)] for i in range(n)]
dp=[[0 for j in range(n)] for i in range(n)]
ru=[0]
for i in range(n):
    ru.append(ru[-1]+a[i])
def f(l,r):
    if flag[l][r]==1:
        return dp[l][r]
    flag[l][r]=1
    if l==r:
        return 0
    fans=10**20
    for m in range(l,r):
        fans=min(fans,f(l,m)+f(m+1,r))
    dp[l][r]=fans+ru[r+1]-ru[l]
    return dp[l][r]

ans=f(0,n-1)
print(ans)

Solution (Python):
INF = 10**18


def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    dp = [[INF]*(N+1) for _ in range(N)]
    cost = [[INF]*(N+1) for _ in range(N)]

    for i in range(N):
        dp[i][i+1] = A[i]
        cost[i][i+1] = 0

    for w in range(2, N+1):
        for le in range(N-w+1):
            ri = le + w
            for i in range(le+1, ri):
                if dp[le][ri] >= dp[le][i] + dp[i][ri]:
                    dp[le][ri] = dp[le][i] + dp[i][ri]
                    cost[le][ri] = min(cost[le][ri],
                                       cost[le][i] + cost[i][ri] + dp[le][ri])

    print(cost[0][N])


if __name__ == '__main__':
    main()

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
C=[0]
for i in range(N):
  C.append(C[i]+A[i])
INF=10**18
DP=[[INF]*N for i in range(N)]
def f(l,r):
  if l==r:
    return 0
  if DP[l][r]!=INF:
    return DP[l][r]
  for i in range(l+1,r+1):
    DP[l][r]=min(DP[l][r],f(l,i-1)+f(i,r)+C[r+1]-C[l])
  return DP[l][r]

print(f(0,N-1))

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from itertools import accumulate
n = int(input())
A = [0] + list(map(int, input().split()))
B = tuple(accumulate(A))
dp = [[-1]*(n+1) for _ in range(n+1)]
def f(i, j):
  if i == j:
    return 0
  if dp[i][j] != -1:
    return dp[i][j]
  if j-i == 1:
    dp[i][j] = A[i]+A[j]
    return dp[i][j]
  res = float("inf")
  for m in range(i, j):
    res = min(res, f(i,m)+f(m+1,j)+(B[j]-B[i-1]))
  dp[i][j] = res
  return res
ans = f(1, n)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  

import numpy as np
from functools import partial
array = partial(np.array, dtype=np.int64)
zeros = partial(np.zeros, dtype=np.int64)
full = partial(np.full, dtype=np.int64)

ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def a_int(): return int(readline())


def ints(): return np.fromstring(readline(), sep=' ', dtype=np.int64)

'''
DPじゃなくて貪欲に小さい方からくっつけるのじゃだめ？←隣り合うという制約が入れられない

sum a_i から をaiに分解するイメージ
dp[i,j] ... コストの最小. A[i:j]を合体させたとき

更新式
dp[i,j] = min(dp[i,i+1] + dp[i+1,j],
              dp[i,i+2] + dp[i+2,j],...
              ) + sum(A[i,j])

dp[i,i+1]=0かな？
'''


N = a_int()
A = ints()
A_accum = zeros(N + 1)
A_accum[1:] = np.cumsum(A)
dp = full((N + 1, N + 1), -1)
dp[np.arange(N), np.arange(N) + 1] = 0

from numba import njit


@njit('(i8,i8,i8[:,:],i8[:])', cache=True)
def dfs(i, j, dp, A_accum):
    if dp[i, j] != -1:
        return dp[i, j]
    mi = 10**14
    for k in range(i + 1, j):
        mi = min(mi, dfs(i, k, dp, A_accum) + dfs(k, j, dp, A_accum))
    dp[i, j] = mi + A_accum[j] - A_accum[i]
    return dp[i, j]


print(dfs(0, N, dp, A_accum))

Solution (Python):


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase




from bisect import bisect_right as br
from bisect import bisect







BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)







mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  


def out(var): sys.stdout.write(str(var))  


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  


def testcase(t):
    for p in range(t):
        solve()


from collections import defaultdict, deque


class Graph(object):
    def __init__(self, dic):
        self.dict = dic
        self.vertex = set()

    def addedge(self, a, b):
        if self.dict[a] == []:
            self.vertex.add(a)
        if b != None:
            self.dict[a].append(b)

    def con_com_util(self, i, unvisited, count, comp):
        for j in self.dict[i]:
            if j in unvisited:
                unvisited.remove(j)
                comp[count].append(j)
                comp = self.con_com_util(j, unvisited, count, comp)
        return comp

    def conn_components(self):
        unvisited = self.vertex.copy()
        count = 0
        comp = defaultdict(list)
        while unvisited:
            i = unvisited.pop()
            comp[count].append(i)
            comp = self.con_com_util(i, unvisited, count, comp)
            count += 1
        return (count, comp)


def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count


n=int(inp())
ar=lis()
inf=float("inf")
dp=[[inf for i in range(n+5)] for _ in range(n+5)]
for i in range(n):
    dp[i][i]=0
prefix=[0,ar[0]]
for i in range(1,n):
    prefix.append(prefix[i]+ar[i])
for i  in range(n-1,-1,-1):
    for j in range(i+1,n):
        for k in range(0,j-i):
            dp[i][j]=min(dp[i][j],(dp[i][i+k]+dp[i+k+1][j])+prefix[j+1]-prefix[i])

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

Solution (Python):
import numpy as np
from numba import njit

N = int(input())
slimes = np.array(list(map(int, input().split())), dtype='int64')
csum_slimes = [0]
for i in range(N):
    csum_slimes.append(csum_slimes[-1]+slimes[i])
csum_slimes = np.array(csum_slimes, dtype='int64')

dpt = np.full((N, N), -1, dtype='int64')

@njit(cache=True)
def get_min_cost(l, r, slimes, dpt, csum_slimes):
    if dpt[l][r] != -1:
        return dpt[l][r]
    if l == r:
        return 0
    min_cost = 10**18
    for m in range(l, r):
        min_cost = min(min_cost, get_min_cost(l,m,slimes,dpt,csum_slimes)+get_min_cost(m+1,r,slimes,dpt,csum_slimes)+csum_slimes[r+1]-csum_slimes[l])
    dpt[l][r] = min_cost
    return min_cost
    

print(get_min_cost(0, N-1, slimes, dpt, csum_slimes))

Solution (Python):
import numpy as np
from numba import njit
N=int(input())
a=np.array([int(i) for i in input().split()],dtype=np.int64)

s=[0]

dp=np.array([[-1 for i in range(N)] for _ in range(N)],dtype=np.int64)

for i in range(1,N+1):
    s.append(s[i-1]+a[i-1])

s=np.array(s,dtype=np.int64)
for i in range(N):
    dp[i][i]=0

@njit('i8(i8,i8,i8[:,:],i8[:])', cache=True)
def calc(i,j,dp,s):
    if dp[i][j]!=-1:
        return dp[i][j]
    m=10**14
    for k in range(i,j):
        m=min(m,calc(i,k,dp,s)+calc(k+1,j,dp,s)+s[j+1]-s[i])
    dp[i][j]=m
    return dp[i][j]

print(calc(0,N-1,dp,s))

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
lis=LI()
dp=[[-1]*n for i in range(n)]
acc=list(accumulate(lis))
for i in range(n):
    dp[i][i]=0
def memo(x,y):
    if dp[x][y]>=0:
        return dp[x][y]
    res=inf
    for i in range(x,y):
        if x==0:
            if acc[y]+memo(x,i)+memo(i+1,y)<res:
                res=acc[y]+memo(x,i)+memo(i+1,y)
        else:
            if acc[y]-acc[x-1]+memo(x,i)+memo(i+1,y)<res:
                res=acc[y]-acc[x-1]+memo(x,i)+memo(i+1,y)
    dp[x][y]=res
    return res
        
for i in range(n):
    for j in range(i,n):
        memo(i,j)

print(dp[0][-1])

Solution (Python):
n=int(input())
A = list(map(int,input().split()))
from itertools import accumulate
S = [0] + list(accumulate(A))
dp = [[0]*(n+1) for _ in range(n+1)]
for d in range(2,n+1):
    for i in range(n-d+1):
        j = i+d


        val = float('inf')
        for k in range(i+1,j):
            val = min(val,dp[i][k]+dp[k][j])
        dp[i][j] += S[j]-S[i] + val
print(dp[0][-1])

Solution (Python):






import sys
input = sys.stdin.readline
sys.setrecursionlimit(500000)

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




def ACC1(l):
  N = len(l)
  ret = [0]*(N+1)
  for i in range(N):
    ret[i+1] = ret[i]+l[i]
  return ret
N = I()
A = IL()
ACC = ACC1(A)

dp = [[INF for r in range(N)] for l in range(N)]

for i in range(N):
  dp[i][i] = 0
  
for h in range(2,N+1):
  for k in range(N+1-h):
    dp[k][k+h-1] = min(dp[k][t]+dp[t+1][k+h-1]+ACC[k+h]-ACC[k] for t in range(k,k+h-1))
    
print(dp[0][-1])

Solution (Python):
import itertools
n=int(input())
a=list(map(int,input().split()))

sumx=[0]+list(itertools.accumulate(a))

dp=[[0]*(n+1) for i in range(n+1)]

for distance in range(2,n+1):
  for i in range(n-distance+1):
    j=i+distance
    dp[i][j]=sumx[j]-sumx[i]+min(dp[i][k]+dp[k][j] for k in range(i+1,j))

print(dp[0][-1])

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
A = LI()
acc = [0] + list(accumulate(A))
dp = [[0] * n for _ in range(n)]

def f(l, r):
    if dp[l][r] or l == r:
        return dp[l][r]
    m = INF
    for i in range(l, r):
        m = min(m, f(l, i) + f(i + 1, r) + acc[r + 1] - acc[l])
    dp[l][r] = m
    return m

print(f(0, n-1))

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
A = LI()
acc = [0] + list(accumulate(A))
dp = [[0] * n for _ in range(n)]

def f(l, r):
    if dp[l][r]:
        return dp[l][r]
    if l == r:
        return 0
    m = INF
    for i in range(l, r):
        m = min(m, f(l, i) + f(i + 1, r) + acc[r + 1] - acc[l])
    dp[l][r] = m
    return m

print(f(0, n-1))

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy


import heapq
sys.setrecursionlimit(10**6)

N = int(input())
a = [0] + list(map(int, input().split())) + [0]
INF = float("inf")

sum_a = list(itertools.accumulate(a))

dp = [[INF]*(N+5) for i in range(N+5)]
for i in range(1,N+1):
    dp[i][i+1] = 0

for k in range(2,N+1):
    for l in range(1,N-k+2):
        r = l + k
        for i in range(r-l-1):
            w1 = sum_a[l+i] - sum_a[l-1]
            w2 = sum_a[r-1] - sum_a[l+i]
            dp[l][r] = min(dp[l][r], dp[l][l+i+1] + dp[l+i+1][r] + w1 + w2)

print(dp[1][N+1])

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
n=int(input())
a=list(map(int,input().split()))
dp=[[10**18]*(n) for _ in range(n)]
flag=[[0]*n for _ in range(n)]
accum=[a[0]]
for i in range(1,n):
    accum.append(accum[-1]+a[i])
accum=[0]+accum
def f(l,r):
    if l==r:
        return 0
    if flag[l][r]:
        return dp[l][r]
    flag[l][r]=1
    ret=10**18
    for i in range(l,r):
        ret=min(ret,f(l,i)+f(i+1,r))
    dp[l][r]=ret+accum[r+1]-accum[l]
    return dp[l][r]
f(0,n-1)
print(dp[0][n-1])

Solution (Python):
from sys import stdin
n = int(stdin.readline())
arr = list(map(int,stdin.readline().split()))
dp = [[0]*n for _ in range(n)]
dp1 = [[0]*n for _ in range(n)]
for i in range(n-1):
    dp1[i][i] = arr[i]
    dp[i][i+1] = arr[i]+arr[i+1]
    dp1[i][i+1] = arr[i]+arr[i+1]
dp1[-1][-1] = arr[-1]
for i in range(n-3,-1,-1):
    for j in range(i+2,n):
        dp[i][j] = 10**20
        for k in range(j-1,i-1,-1):
            dp[i][j] = min(dp[i][j],dp[i][k]+dp1[i][k]+dp[k+1][j]+dp1[k+1][j])
        dp1[i][j] = dp1[i][j-1]+arr[j]
print(dp[0][-1])

Solution (Python):
from itertools import groupby, accumulate, product, permutations, combinations
def solve():
  N = int(input())
  A = list(map(int, input().split()))
  cum = [0]+list(accumulate(A))
  dp = [[float('inf')]*N for _ in range(N)]
  for i in range(N):
    dp[i][i] = 0
  for i in range(N-1):
    dp[i][i+1] = A[i]+A[i+1]
  for k in range(2,N):
    for i in range(N):
      j = i+k
      if j>N-1:
        break
      for l in range(i,j):
        dp[i][j] = min(dp[i][j],dp[i][l]+dp[l+1][j])
      dp[i][j] += cum[j+1]-cum[i]
  ans = dp[0][-1]
  return ans
print(solve())

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
dp = [[0] * (n+1) for _ in range(n+1)]
s = [0] * (n+1)
for i in range(n):
    s[i+1] = s[i] + a[i]
for l in range(2, n+1):
    for i in range(n-l+1):
        j = i + l
        dp[i][j] = s[j] - s[i] + min(dp[i][k] + dp[k][j] for k in range(i+1, j))
print(dp[0][n])

Solution (Python):
n=int(input())
arr=list(map(int,input().split()))
dp=[[[10**18,10**18] for _ in range(n)] for _ in range(n)]
for i in range(n):
  dp[i][i][0]=arr[i]
  dp[i][i][1]=0
for i in range(1,n):
  for j in range(n-i):
    for k in range(i):
      if dp[j][j+i][1]>dp[j][j+k][0]+dp[j+k+1][j+i][0]+dp[j][j+k][1]+dp[j+k+1][j+i][1]:
        dp[j][j+i][1]=dp[j][j+k][0]+dp[j+k+1][j+i][0]+dp[j][j+k][1]+dp[j+k+1][j+i][1]
        dp[j][j+i][0]=dp[j][j+k][0]+dp[j+k+1][j+i][0]
print(dp[0][n-1][1])

Solution (Python):
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue



sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))




def main():
    n = ni()
    a = na()
    a.append(INF)

    
    dp = [[0 if _ == __ else INF for _ in range(n + 1)] for __ in range(n + 1)]

    for i in range(n):
        dp[i][i + 1] = 0

    for d in range(2, n + 1):
        for i in range(n + 1 - d):
            j = i + d
            total = sum(a[i:j])
            for k in range(1, d):
                dp[i][j] = min(dp[i][j], dp[i][i + k] + dp[i + k][j] + total)

    print(dp[0][n])


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())

arr = list(map(int, input().split()))


sums = [0 for i in range(len(arr))]

sums[0] = arr[0]

for i in range(1, len(sums)):
    sums[i] = sums[i-1] + arr[i]


sums.insert(0, 0)
dp = []

for i in range(n):
    temp = []
    for j in range(n):
        temp.append(0)
    
    dp.append(temp)


for i in range(1, n):
    for j in range(0, n-i):
        start = j
        end = start + i

        min_ = float('inf')
        for k in range(start, end):
            min_ = min(min_, dp[start][k] + dp[k+1][end] + sums[end+1] - sums[start])
        
        dp[start][end] = min_


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

Solution (Python):
import sys
input = sys.stdin.readline

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

D = [-1] * (n**2)
for i in range(n):
    D[i*n + i] = 0

S = [A[0]]
for i in range(1, n):
    S.append(A[i] + S[-1])
S.append(0)




def merge(l, r):
    
    if D[l*n + r] != -1:
        return D[l*n + r]
    else:
        ans = float("inf")
        for i in range(l, r):
            ans = min(ans, merge(l, i) + merge(i+1, r) + S[r] - S[l-1])
        D[l*n + r] = ans
        return ans

print(merge(0, n-1))

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


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  


N = ni()

a_array = na()
sum_array = [0]
slime = 0
for a in a_array:
    slime += a
    sum_array.append(slime)

INF = 10 ** 15
ans = [[INF] * N for _ in range(N)]


def solve(l, r):
    
    if ans[l][r] != INF:
        return ans[l][r]
    if l == r:
        ans[l][r] = 0
        
        return 0
    slime_sum = sum_array[r+1] - sum_array[l]
    
    for i in range(l, r):
        ans[l][r] = min(ans[l][r], solve(l, i) + solve(i+1, r) + slime_sum)
    
    return ans[l][r]


print(solve(0, N-1))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
dp = [[0] * (n+1) for _ in range(n+1)]
s = [0] * (n+1)
for i in range(n):
    s[i+1] = s[i] + a[i]
for l in range(2, n+1):
    for i in range(n-l+1):
        j = i + l
        dp[i][j] = s[j] - s[i] + min(dp[i][k] + dp[k][j] for k in range(i+1, j))
print(dp[0][n])

Solution (Python):
import sys
readline = sys.stdin.readline





N = int(readline())
A = list(map(int,readline().split()))

A = [0] + A
for i in range(1,len(A)):
  A[i] += A[i - 1]

INF = 10 ** 18
dp = [[INF] * N for i in range(N)]
for i in range(N):
  dp[i][i] = 0


for i in range(N): 
  for l in range(N - i):
    r = l + i
    
    
    cums = A[r + 1] - A[l]
    for m in range(l,r):
      if dp[l][m] + dp[m + 1][r] + cums < dp[l][r]:
        dp[l][r] = dp[l][m] + dp[m + 1][r] + cums
        
print(dp[0][-1])

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N = INT()
a = [0]+LIST()
a_acc = list(accumulate(a))
dp = [[None]*(N+1) for _ in range(N+1)]

def rec(l, r):
    if dp[l][r]: return dp[l][r] 
    if l == r:
        return 0
    mi = INF
    for i in range(l, r):
        mi = min(mi, rec(l, i)+rec(i+1, r))
    dp[l][r] = mi + (a_acc[r]-a_acc[l-1])
    return dp[l][r]

print(rec(1, N))

Solution (Python):
import sys
sys.setrecursionlimit(10000)
N = int(input())
a = list(map(int, input().split()))
suma = [0, a[0]]
for i in range(1, N):
    suma.append(suma[-1] + a[i])
inf = float("inf")
dp = [[-1 for i in range(N+1)] for j in range(N+1)]



def rec(l, r):
    if r - l == 0:
        dp[l][r] = 0
        return 0
    elif r - l == 1:
        dp[l][r] = a[l]
        return a[l]

    if dp[l][r] != -1:
        return dp[l][r]

    
    
    res = inf
    for pos in range(l+1, r):
        tmp = 0
        if pos - l > 1:
            tmp += rec(l, pos) + suma[pos] - suma[l]
        else:
            tmp += rec(l, pos)
        if r - pos > 1:
            tmp += rec(pos, r) + suma[r] - suma[pos]
        else:
            tmp += rec(pos, r)
        res = min(res, tmp)
    dp[l][r] = res
    return res

print(rec(0, N))

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

def cumsum(a):
    """l[i] = sum(a[:i]) なるlを返す
    sum(a[i:j]) == l[j+1] - l[i]
    """
    c = 0
    l = [None] * (len(a)+1)
    for i,num in enumerate(a):
        l[i] = c
        c += num
    l[-1] = c
    return l
s = cumsum(a)

dp = [[None]*n for _ in range(n+1)] 
for j in range(n):
    dp[1][j] = 0
for i in range(2,n+1):
    for j in range(n-i+1):
        dp[i][j] = min(dp[k][j]+dp[i-k][j+k] for k in range(1,i)) + s[j+i] - s[j]
print(dp[n][0])

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

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

for i in range(N):
    for j in range(i,N):
        size[i][j] = sum(a[i:j+1])

for i in range(N-2, -1, -1):
    for j in range(i+1, N):
        dp[i][j] = min([dp[i][k] + dp[k+1][j] + size[i][k] + size[k+1][j] for k in range(i, j)])

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