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 sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
最後の2つを決める：[0,x) [x,N)
小問題2つに分割できる。
全ての連続区間を計算すればよい
"""

N = int(input())
A = np.array(input().split(), np.int64)


Acum = np.zeros((N,N+1), dtype=np.int64)
for L in range(N):
    Acum[L,L+1:] = A[L:].cumsum()

dp = np.zeros((N,N+1), dtype=np.int64)
for size in range(2,N+1):
    for L in range(N-size+1):
        R = L + size
        dp[L,R] = (dp[L,L+1:R] + dp[L+1:R,R]).min() + Acum[L,R]

answer = dp[0,N]
print(answer)

Solution (Python):
n = int(input())
s = list(map(int,input().split()))
dp = [[0 for _ in range(n)] for _ in range(n)]
psum = [0 for _ in range(n+1)]
sm = 0
for i in range(n):
    sm +=s[i]
    psum[i+1]=sm
def findMin(left,right):
    dp[left][right]=dp[left][left]+dp[left+1][right]+psum[right+1]-psum[left]
    for i in range(left+1,right):
        dp[left][right] = min(dp[left][right],dp[left][i]+dp[i+1][right]+psum[right+1]-psum[left])
for length in range(2,n+1):
    for l in range(n-length+1):
        r = l+length-1
        findMin(l,r)

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

Solution (Python):
n = int(input())
s = list(map(int,input().split()))
dp = [[0 for _ in range(n)] for _ in range(n)]
psum = [0 for _ in range(n+1)]
sm = 0
for i in range(n):
    sm +=s[i]
    psum[i+1]=sm
def findMin(left,right):
    dp[left][right]=dp[left][left]+dp[left+1][right]+psum[right+1]-psum[left]
    for i in range(left+1,right):
        dp[left][right] = min(dp[left][right],dp[left][i]+dp[i+1][right]+psum[right+1]-psum[left])
for length in range(2,n+1):
    for l in range(n-length+1):
        r = l+length-1
        findMin(l,r)

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

Solution (Python):
import sys
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = IL()

dp = [[0]*(N+1) for i in range(N+1)]
data = [[0]*(N+1) for i in range(N+1)] 
for i in range(N):
  data[i][i+1] = a[i]
for i in range(N+1):
  for j in range(N+1):
    if i+j <= N:
      data[j][i+j] = sum(a[j:i+j])
    else:
      break

for i in range(2,N+1):
  for j in range(N+1):
    if i+j <= N:
      tmp = MAX_INT
      for k in range(1,i):
        tmp = min(tmp,dp[j][k+j] + dp[k+j][i+j])
      dp[j][i+j] = tmp + data[j][i+j]
    else:
      break



print(dp[0][N])

Solution (Python):


import sys

class NSlimes:
    def solve(self):
        n = int(input())
        a = [None] + [int(_) for _ in input().split()]

        dp = [[float('inf')] * (n + 1) for _ in range(n + 1)]
        for i in range(1, n + 1):
            dp[i][i] = 0
        for i in range(n + 1, 0, -1):
            for j in range(1, n + 1):
                s = sum(a[p] for p in range(i, j + 1))
                for k in range(i, j):
                    dp[i][j] = min(dp[i][k] + dp[k + 1][j] + s, dp[i][j])

        print(dp[1][n])


        

        
        
        
        
        
        
        
        
        
        
        
        
        
        
        

solver = NSlimes()
input = sys.stdin.readline

solver.solve()

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

DP = [[[0] * 2 for _ in range(N)] for _ in range(N + 1)]
for i in range(N):
  DP[1][i] = [a[i], 0]

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

print(DP[N][0][1])

Solution (Python):
N=int(input())
A=list(map(int,input().strip().split(" ")))
dp=[[10**20]*len(A)  for i in range(0,len(A)+1)]

pre=[]
temp=0
for i in range(len(A)):
    temp+=A[i]
    pre+=[temp]
length=1
for i in range(len(A)):
    dp[length][i]=0

for L in range(2,len(A)+1):
    for start in range(0,len(A)-L+1):
        for j in range(start+1,start+L):
            if start>0:
                dp[L][start]=min(dp[j-start][start]+dp[L-j+start][j]+pre[start+L-1]-pre[start-1],dp[L][start])
            else:
                dp[L][start]=min(dp[j-start][start]+dp[L-j+start][j]+pre[start+L-1],dp[L][start])
print(dp[len(A)][0])

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [list(map(list, sys.stdin.readline().split())) for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
intINF = int(1e15)
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N = I()
a = LI()

dp = [[intINF]*(N+1) for i in range(N+1)]
acc = [0]*(N+1)
for i in range(N):
    acc[i+1] = acc[i] + a[i]

for i in range(N-1):
    dp[i][i+2] = a[i]+a[i+1]
    dp[i][i+1] = 0
    dp[i][i] = 0
dp[N-1][N] = 0
dp[N-1][N-1] = 0
dp[N][N] = 0

for l in range(N-1)[::-1]:
    for r in range(l, N+1):
        for k in range(l+1,r):
            dp[l][r] = min(dp[l][r], dp[l][k]+dp[k][r]+(acc[r]-acc[l]))

print(dp[0][N])

Solution (Python):
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)

N = int(input())
a = list(map(int, input().split()))
dp = [[0] * (N + 1) for _ in range(N + 1)]

sum = [0] * (N + 1) 
inf = float('inf')

for i in range(N):
	sum[i + 1] = sum[i] + a[i]
	
for c in range(2, N + 1):
	for i in range(N - c + 1):
		ans = inf
		for k in range(1, c):
			tmp = dp[i][i + k] + dp[i + k][i + c] + sum[i + c] - sum[i]
			if tmp < ans:
				ans = tmp
				
		dp[i][i + c] = ans
		
print(dp[0][N])

Solution (Python):
inf = float('inf')

def accmulate(array):
    global cs
    cs = [0]*(len(array)+1)
    for i in range(len(array)):
        cs[i+1] = cs[i] + array[i]

def query(l,r):
    return cs[r+1] - cs[l]

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

accmulate(A)

dp = [[inf]*(N+1) for _ in range(N+1)]

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

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

ans = dp[0][N]
print(ans)

Solution (Python):
inf = float('inf')

def accmulate(array):
    global cs
    cs = [0]*(len(array)+1)
    for i in range(len(array)):
        cs[i+1] = cs[i] + array[i]

def query(l,r):
    return cs[r+1] - cs[l]

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

accmulate(A)

dp = [[inf]*(N+1) for _ in range(N+1)]

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

for i in range(N-1):
    dp[i][i+2] = A[i] + A[i+1]

for b in range(3,N+1):
    for i in range(N-b+1):
        j = i + b
        for k in range(i+1,j):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + query(i,j-1))

ans = dp[0][N]
print(ans)

Solution (Python):
import fileinput


def solve_slimes(slimes):
    slime_union_table = [0] * len(slimes) * len(slimes)
    slime_cost_table = [0] * len(slimes) * len(slimes)

    for i in range(len(slimes)):
        slime_union_table[i] = slimes[i]

    for gap in range(1, len(slimes)):
        for li in range(len(slimes) - gap):
            split_size = slime_union_table[li] + slime_union_table[li + 1 + (gap - 1) * len(slimes)]
            slime_union_table[li + gap * len(slimes)] = split_size

            for split in range(0, gap):
                split_cost = slime_cost_table[li + split * len(slimes)] + slime_cost_table[li + split + 1 + (gap - split - 1) * len(slimes)] + split_size

                if slime_cost_table[li + gap * len(slimes)] == 0:
                    slime_cost_table[li + gap * len(slimes)] = split_cost

                else:
                    slime_cost_table[li + gap * len(slimes)] = min(
                        split_cost,
                        slime_cost_table[li + gap * len(slimes)]
                    )
    return slime_cost_table[len(slimes) * (len(slimes) - 1)]


inp = fileinput.FileInput()

inp.readline()
slimes = [int(v) for v in inp.readline().split()]

print(solve_slimes(slimes))

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
INF = float('inf')
N = int(input())
a = list(map(int,input().split()))
cum = [0]*(N+1)
for i in range(N):
    cum[i] = cum[i-1]+a[i]
dp = [[-1]*N for _ in range(N)]
for i in range(N):
    dp[i][i] = 0

def cal(i,j):
    if dp[i][j] != -1:
        return dp[i][j]
    else:
        res = INF
        for k in range(i,j):
            res = min(res,cal(i,k)+cal(k+1,j)+cum[j]-cum[i-1])
        dp[i][j] = res
        return res

print(cal(0,N-1))

Solution (Python):
def calcdp(i,j):
    global dp, A, BIG_INT
    
    if dp[i][j] != -1:
        return dp[i][j]
    
    if i + 1== j:
        dp[i][j] = 0
        return dp[i][j]
    
    elif i + 2== j:
        dp[i][j] = A[i] + A[i + 1]
        return dp[i][j]
    
    else:
        m = BIG_INT
        for k in range(i + 1, j):
            m = min(calcdp(i, k) + calcdp(k, j), m)
        m += sum(A[i:j])
        dp[i][j] = m
        return dp[i][j]

    
BIG_INT = 10**30
N = int(input())
A = [int(x) for x in input().split()]
dp = [[-1] * (N + 1) for _ in range(N)] 

print(calcdp(0, N))

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

Solution (Python):



n=int(input())
aa = [int(i) for i in input().split()]
import sys
sys.setrecursionlimit(10**7)
from itertools import accumulate

acc = list(accumulate([0]+aa))

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

def dp(r,l):
    if memo[r][l] > 0:
        return memo[r][l]
    if r-l==1:
        memo[r][l] = 0
        return 0
    res=0
    res = min([dp(c,l) + dp(r,c) for c in range(l+1,r)])
    res += acc[r]- acc[l]

    memo[r][l] = res
    return res

dp(n,0)
print(memo[n][0])

Solution (Python):


import itertools as it

INF = 1 << 62
N = int(input())
xs = [int(s) for s in input().split()]
acc = list(it.accumulate([0] + xs))

dp = [[INF] * (N + 1) for _ in range(N)]

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

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

print(dp[0][N])

Solution (Python):
def rec(frm, to):
    """return: [frm,to)の合体コスト最小値"""
    if to - frm == 1:
        return 0

    if memo[frm][to]:
        return memo[frm][to]

    res = inf
    for mid in range(frm + 1, to):
        res = min(res, rec(frm, mid) + rec(mid, to))
    res += cum_sum[to] - cum_sum[frm]

    memo[frm][to] = res
    return res


inf = float('inf')

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

cum_sum = [0] * (n + 1)
for i, aa in enumerate(a):
    cum_sum[i + 1] = cum_sum[i] + aa

memo = [[None] * (n + 1) for _ in range(n + 1)]


print(rec(0, n))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
dp = [[float("inf")] * n for _ 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 w in range(1, n):
    for i in range(n - w):
        for j in range(i, i + w):
            dp[i][i + w] = min(dp[i][i + w], dp[i][j] + dp[j + 1][i + w] + s[i + w + 1] - s[i])
print(dp[0][n - 1])

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


dp = [[float("inf")]*(n+1) for i in range(n+1)]
for i in range(n):
    dp[i][i] = 0


cost = [0]*(n+1)
for i in range(n):
    cost[i+1] = cost[i] + a[i]


def dfs(l, r):
    if not isinf(dp[l][r]):
        return dp[l][r]
    elif (r - l) == 1:
        dp[l][r] = 0
        return dp[l][r]
    else:
        res = float("inf")
        for k in range(l + 1, r):
            
            res = min(res, dfs(l, k) + dfs(k, r) + (cost[r] - cost[l]))
        dp[l][r] = res
    return dp[l][r]

dfs(0, n)
print(dp[0][n])

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


dp = [[float("inf")]*(n+1) for i in range(n+1)]
for i in range(n):
    dp[i][i] = 0


cost = [0]*(n+1)
for i in range(n):
    cost[i+1] = cost[i] + a[i]


def dfs(l, r, infnum):
    if dp[l][r] != infnum:
        return dp[l][r]
    elif (r - l) == 1:
        dp[l][r] = 0
        return dp[l][r]
    else:
        res = float("inf")
        for k in range(l + 1, r):
            
            res = min(res, dfs(l, k, infnum) + dfs(k, r, infnum) + (cost[r] - cost[l]))
        dp[l][r] = res
    return dp[l][r]

dfs(0, n, float("inf"))
print(dp[0][n])

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


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


cost = [0]*(n+1)
for i in range(n):
    cost[i+1] = cost[i] + a[i]


def dfs(l, r):
    if dp[l][r] != -1:
        return dp[l][r]
    elif (r - l) == 1:
        dp[l][r] = 0
        return dp[l][r]
    else:
        res = float("inf")
        for k in range(l + 1, r):
            
            res = min(res, dfs(l, k) + dfs(k, r) + (cost[r] - cost[l]))
        dp[l][r] = res
    return dp[l][r]

dfs(0, n)
print(dp[0][n])

Solution (Python):
def f(n, a):
    inf = float("inf")
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 2, -1, -1):
        s = a[i]
        dpi = dp[i]
        for j in range(i + 1, n):
            mn = inf
            s += a[j]
            for d in range(i, j):
                k = dpi[d] + dp[d + 1][j]
                if k < mn:
                    mn = k
            dpi[j] = mn + s
    return dp[0][-1]


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

Solution (Python):
def f(n, a):
    inf = float("inf")
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 2, -1, -1):
        s = a[i]
        dpi = dp[i]
        for j in range(i + 1, n):
            mn = inf
            s += a[j]
            for d in range(i, j):
                k = dpi[d] + dp[d + 1][j]
                if k < mn:
                    mn = k
            dpi[j] = mn + s
    return dp[0][-1]


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

Solution (Python):
def f(n, a):
    inf = float("inf")
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 2, -1, -1):
        s = a[i]
        dpi = dp[i]
        for j in range(i + 1, n):
            mn = inf
            s += a[j]
            for d in range(i, j):
                k = dpi[d] + dp[d + 1][j]
                if k < mn:
                    mn = k
            dpi[j] = mn + s
    return dp[0][-1]


n = int(input())
a = tuple(map(int, input().split()))
print(f(n, a))

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

dp = [[-1]*n for i in range(n)]
for i in range(n):
    dp[i][i] = 0
cumsum = [0]
for i in range(n):
    cumsum.append(cumsum[-1] + a[i])

def calc_cost(left, right):
    if dp[left][right] >= 0:
        return dp[left][right]
    min_ = min(calc_cost(left, i) + calc_cost(i+1, right) for i in range(left, right))
    dp[left][right] = cumsum[right+1]-cumsum[left] + min_
    return dp[left][right]

print(calc_cost(0,n-1))

Solution (Python):


from itertools import accumulate as accum
import sys
input = sys.stdin.readline

def f2(n, a):
    acsum = list(accum(a)) + [0]
    dp = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 0
        if i + 1 != n:
            dp[i][i + 1] = a[i] + a[i + 1]
    for i in range(n - 3, -1, -1):
        for j in range(i + 2, n):
            c = float('inf')
            dpi = dp[i]
            for x in range(i, j):
                c_ = dpi[x] + dp[x + 1][j]
                if c_ < c:
                    c = c_
            dpi[j] = c + acsum[j] - acsum[i - 1]
    return(dp[0][n - 1])

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

Solution (Python):


from itertools import accumulate as accum
import sys
input = sys.stdin.readline

def f2(n, a):
    acsum = list(accum(a)) + [0]
    dp = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 0
        if i + 1 != n:
            dp[i][i + 1] = a[i] + a[i + 1]
    for i in range(n - 3, -1, -1):
        for j in range(i + 2, n):
            c = float('inf')
            dpi = dp[i]
            for x in range(i, j):
                c_ = dpi[x] + dp[x + 1][j]
                if c_ < c:
                    c = c_
            dpi[j] = c + acsum[j] - acsum[i - 1]
    return(dp[0][n - 1])

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

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

INF = 10 ** 20

dp = [[0 for _ in range(n)] for _ in range(n)]

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


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

for k in range(1, n):
    for x in range(n-k):
        y = x + k
        temp = INF
        for i in range(k):
            temp = min(temp, dp[x][x+i] + dp[x+i+1][y] + s[y+1] - s[x])
        dp[x][y] = temp

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

Solution (Python):
import sys
input=sys.stdin.readline
from itertools import accumulate
n=int(input())
A=[0]+list(accumulate(map(int,input().split())))
DP=[[0]*n for _ in range(n)]
for d in range(1,n):
    for i in range(n-d):
        j=i+d
        tmp=float('inf')
        for k in range(i,j):
            tmp=min(tmp,DP[i][k]+DP[k+1][j])
        DP[i][j]=tmp+A[j+1]-A[i]
print(DP[0][n-1])

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
a = tuple(map(int,input().split()))


b = [0]*(n+1)
for i in range(n):
    b[i+1] = b[i]+a[i]


dp = [[0]*n for i in range(n)]
for j in range(1,n):
    for i in range(n-j):
        
        mi = float("inf")
        for k in range(i,i+j):
            mi = min(mi,dp[i][k]+dp[k+1][i+j])
        dp[i][i+j] = mi+b[i+j+1]-b[i]

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

Solution (Python):
def get_cost(l, r):
    
    if memo[l][r] < INF: return memo[l][r]
    if r == l: return 0

    t = INF
    for m in range(l, r):
        t = min(t, get_cost(l, m) + get_cost(m + 1, r))
    memo[l][r] = t + (c_sum[r] - c_sum[l - 1])
    return memo[l][r]


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

c_sum = [0]
for aa in a:
    c_sum.append(c_sum[-1] + aa)


INF = float('inf')

memo = [[INF for _ in range(N + 1)] for _ in range(N + 1)]


print(get_cost(1, N))

Solution (Python):



def div_cost(left, right):
    
    if bl_calculated[left][right]:
        return memo[left][right]
    bl_calculated[left][right] = True
    if left == right:
        memo[left][right] = 0
        return memo[left][right]
    divided_to_alone_cost = INF
    
    for mid in range(left, right):
        divided_to_alone_cost = min(divided_to_alone_cost, div_cost(left, mid) + div_cost(mid + 1, right))
    memo[left][right] = divided_to_alone_cost + (c_sum[right] - c_sum[left - 1])
    
    return memo[left][right]


INF = float('inf')

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

c_sum = [0]
for aa in a:
    c_sum.append(c_sum[-1] + aa)


memo = [[0 for _ in range(N + 1)] for _ in range(N + 1)]


bl_calculated = [[False for _ in range(N + 1)] for _ in range(N + 1)]


print(div_cost(1, N))

Solution (Python):

from __future__ import division, print_function

import os
import sys
from atexit import register
from io import BytesIO

range = xrange

sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

n = int(input())
a = [float(i) for i in input().split()]

pref_sums = [0.0] * (n + 1)
for i in range(n):
    pref_sums[i + 1] = pref_sums[i] + a[i]

dp = [[0.0] * n for _ in range(n)]


def solve(start, end):
    if (dp[start][end] == 0.0) and (start != end):
        dp[start][end] = min(
            solve(start, i) + solve(i + 1, end) + pref_sums[end + 1] - pref_sums[start] for i in range(start, end))
    return dp[start][end]


print(int(solve(0, n - 1)))

Solution (Python):

from __future__ import division, print_function

import os
import sys
from atexit import register
from io import BytesIO

range = xrange

sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

n = int(input())
a = [int(i) for i in input().split()]

pref_sums = [0] * (n + 1)
for i in range(n):
    pref_sums[i + 1] = pref_sums[i] + a[i]

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


def solve(start, end):
    if (dp[start][end] == 0) and (start != end):
        dp[start][end] = min(pref_sums[i + 1] - pref_sums[start] + pref_sums[end + 1] - pref_sums[i + 1] +
                             solve(start, i) + solve(i + 1, end) for i in range(start, end))
    return dp[start][end]


print(solve(0, n - 1))

Solution (Python):

import itertools
import sys
sys.setrecursionlimit(100000)
input=lambda : sys.stdin.readline().rstrip('\n')

n=int(input())
d=[0]+list(itertools.accumulate(map(int,input().split())))
memo=[[-1 for i in range(401)]for i in range(401)]
def split_slime(l,r):
    if l+1==r:
        return 0
    if memo[l][r]!=-1:
        return memo[l][r]
    mn=10**18
    for i in range(l+1,r):
        cost=(d[i]-d[l])+(d[r]-d[i])+split_slime(l,i)+split_slime(i,r)
        if mn>cost:
            mn=cost
    memo[l][r]=mn
    return memo[l][r]
print(split_slime(0,n))

Solution (Python):
n = int(input())
A = [int(i) for i in input().split()]

INF = 10 ** 18
DP = [[0] * (n - i) for i in range(n)]

csum_ = [0]
for a in A:
    csum_.append(csum_[-1] + a)

def csum(i, j): 
    return csum_[j] - csum_[i]

for i in range(1, n):
    for j in range(n-i):
        if i > 1:
            DP[i][j] = min(DP[k][j] + DP[i-k-1][j+k+1] for k in range(0, i))

        DP[i][j] += csum(j, j + i + 1)

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

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

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


acum = [0] * (n+1)
for i, ai in enumerate(a):
    acum[i+1] += acum[i] + ai


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


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

print(dp[0][n])

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

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

acum = [0] * (n+1)
for i, ai in enumerate(a):
    acum[i+1] += acum[i] + ai

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

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

print(dp[0][n])

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

    cumsum = [[0]*(N-i+1) for i in range(N+1)]

    dp = [[float("inf")]*(N-i+1) for i in range(N+1)]
    dp[1] = [0] * N
    cumsum[1] = A
    for i in range(2, N+1):
        for j in range(N-i+1):
            cumsum[i][j] = cumsum[i-1][j+1] + A[j]
            for k in range(1, i):
                dp[i][j] = min(dp[k][j] + dp[i-k][j+k] +
                               cumsum[i][j], dp[i][j])
    print(dp[N][0])


if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
A = [int(a) for a in input().split()]
B = [0]
for a in A:
    B.append(B[-1]+a)

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

for d in range(1, N):
    for l in range(N-d):
        r = l + d
        if d == 0:
            dp[l][r] = A[l]
            
        else:
            dp[l][r] = 10**20
            for m in range(l, r):
                dp[l][r] = min(dp[l][r], dp[l][m] + dp[m+1][r] + B[r+1]-B[l])
    
print(dp[0][N-1])

Solution (Python):
from itertools import accumulate
import sys

sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

dp = [[float(0)]*N for _ in range(N)]
a_acc = [0]+list(accumulate(A))


def dfs(l, r):
    """
    List[l:r]
    """
    if dp[l][r-1] != float('inf'):
        return dp[l][r-1]
    if r-l == 1:
        dp[l][r-1] = 0
        return 0
    if r-l == 2:
        dp[l][r-1] = A[l]+A[r-1]
        return dp[l][r-1]
    else:
        dp[l][r-1] = min(dfs(l, v)+dfs(v, r)
                         for v in range(l+1, r))+a_acc[r]-a_acc[l]
        return dp[l][r-1]


def bfs():
    for d in range(2, N+1):
        for l in range(0, N-d+1):
            r = l + d
            
            tmp = float('inf')
            for m in range(l+1, r):
                tmp = min(tmp, dp[l][m-1]+dp[m][r-1])
            
            
            dp[l][r-1] = tmp+a_acc[r]-a_acc[l]



bfs()

ans = int(dp[0][-1])
print(ans)

Solution (Python):
from itertools import accumulate

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

a_acc = [0] + list(accumulate(a_list))

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

for d in range(2, N + 1):
    for l in range(N + 1 - d):
        r = l + d
        tmp = float("inf")
        for m in range(l+1, r):
            tmp = min(tmp, dp[l][m] + dp[m][r])
        dp[l][r] = tmp + a_acc[r] - a_acc[l]

print(dp[0][N])

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

INF = float('inf')

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

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

prefix = [0]+ list(accumulate(a))

for i in range(1,N):
    for j in range(0,N-i):
        temp = INF
        for k in range(i):
            temp = min(temp,cost[j][j+k] + cost[j+k+1][j+i])
        cost[j][j+i] = temp + prefix[j+i+1] - prefix[j]


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

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

INF = float('inf')

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

cost = [[0]*N for _ in range(N)]
for i in range(N):
    cost[i][i] = 0
prefix = [0]+ list(accumulate(a))

for i in range(1,N):
    for j in range(0,N-i):
        temp = INF
        for k in range(i):
            temp = min(temp,cost[j][j+k] + cost[j+k+1][j+i])
        cost[j][j+i] = temp + prefix[j+i+1] - prefix[j]


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

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

from itertools import accumulate
Accum = list(accumulate([0] + A))

dp = [ [inf]*(N+1) for _ in range(N+1)]

def dfs(l,r):
    if dp[l][r] != inf:
        return dp[l][r]
    if l == r: 
        return 0
    if l+1 == r: 
        dp[l][r] = A[l]
        return A[l]

    local_ans = inf
    for i in range(l+1, r): 
        local_ans = min(local_ans, dfs(l,i) + dfs(i,r))
    dp[l][r] = local_ans + Accum[r] - Accum[l]
    return dp[l][r]
print (dfs(0,N)- sum(A))

Solution (Python):


n = input()
a = map(int, raw_input().split())
oo = sum(a) * n
cumul = [0] * (n + 1)
for i in range(n):
    cumul[i + 1] = cumul[i] + a[i]

dp = [[oo] * n for _ in range(n)]
for i in range(n):
    dp[i][i] = 0
for i in range(1, n):
    for j in range(n - i):
        k = j + i
        for l in range(j, k):
            dp[j][k] = min(dp[j][k], dp[j][l] + dp[l + 1][k])
        dp[j][k] += cumul[k + 1] - cumul[j]
print(dp[0][n - 1])

Solution (Python):


"""
参考：https://kyopro-friends.hatenablog.com/entry/2019/01/12/231035
　　　https://atcoder.jp/contests/dp/submissions/3970847
・メモ化再帰
・累積和
"""

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
aN = LIST()


sm = [0] * (N+1)
for i in range(N):
    sm[i+1] = sm[i] + aN[i]

memo = list2d(N+1, N+1, INF)
def rec(l, r):

    if memo[l][r] != INF: 
        return memo[l][r]
    if l == r:
        return 0
    mn = INF
    
    for m in range(l, r):
        mn = min(mn, rec(l, m) + rec(m+1, r))
    
    memo[l][r] = mn + (sm[r] - sm[l-1])
    return memo[l][r]

print(rec(1, N))