Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate
import sys
# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

dp = [[float('inf')]*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]


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


Fixed submission:
from itertools import accumulate
import sys
# python template for atcoder1
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
            #print("l,r->", l, r)
            tmp = float('inf')
            for m in range(l+1, r):
                tmp = min(tmp, dp[l][m-1]+dp[m][r-1])
            #print("tmp->", tmp)
            #print("acc->", a_acc[r]-a_acc[l])
            dp[l][r-1] = tmp+a_acc[r]-a_acc[l]


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

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

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


def dfs(l, r):
    """
    List[l:r]
    """
    #print("l,r->", l, r)
    # print(A[l:r])
    if dp[l][r-1] != float('inf'):
        return dp[l][r-1]
    if r-l == 1:
        # print("sole")
        return 0
    if r-l == 2:
        # print("double")
        dp[l][r-1] = A[l]+A[r-1]
        return dp[l][r-1]
    elif r-l <= 0:
        # print("err")
        return 0
    else:
        if l+2 >= r:
            #print("err->ret empty")
            return -1
        else:
            # print("update")
            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]


dfs(0, N)
#print("ans->", dp[0][-1])
print(dp[0][-1])


Fixed submission:
from itertools import accumulate
import sys
# python template for atcoder1
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
            #print("l,r->", l, r)
            tmp = float('inf')
            for m in range(l+1, r):
                tmp = min(tmp, dp[l][m-1]+dp[m][r-1])
            #print("tmp->", tmp)
            #print("acc->", a_acc[r]-a_acc[l])
            dp[l][r-1] = tmp+a_acc[r]-a_acc[l]


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

Buggy python submission (verdict: Time Limit Exceeded):
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

dp = [[float('inf')]*N for _ in range(N)]
for i in range(N):
    dp[i][i] = 0


def dfs(l, r):
    """
    List[l:r]
    """
    #print("l,r->", l, r)
    # print(A[l:r])
    if dp[l][r-1] != float('inf'):
        return dp[l][r-1]
    if r-l == 1:
        # print("sole")
        return 0
    if r-l == 2:
        # print("double")
        dp[l][r-1] = A[l]+A[r-1]
        return dp[l][r-1]
    elif r-l <= 0:
        # print("err")
        return 0
    else:
        if l+2 >= r:
            #print("err->ret empty")
            return -1
        else:
            # print("update")
            dp[l][r-1] = min(dfs(l, v)+dfs(v, r)
                             for v in range(l+1, r))+sum(A[l:r])
            return dp[l][r-1]


dfs(0, N)
# print(dp)
#print("ans->", dp[0][-1])
print(dp[0][-1])


Fixed submission:
from itertools import accumulate
import sys
# python template for atcoder1
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
            #print("l,r->", l, r)
            tmp = float('inf')
            for m in range(l+1, r):
                tmp = min(tmp, dp[l][m-1]+dp[m][r-1])
            #print("tmp->", tmp)
            #print("acc->", a_acc[r]-a_acc[l])
            dp[l][r-1] = tmp+a_acc[r]-a_acc[l]


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

Buggy python submission (verdict: Time Limit Exceeded):
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

dp = [[float('inf')]*N for _ in range(N)]
for i in range(N):
    dp[i][i] = 0


def dfs(l, r):
    """
    List[l:r]
    """
    #print("l,r->", l, r)
    # print(A[l:r])
    if dp[l][r-1] != float('inf'):
        return dp[l][r-1]
    if r-l == 1:
        # print("sole")
        return 0
    if r-l == 2:
        # print("double")
        dp[l][r-1] = A[l]+A[r-1]
        return dp[l][r-1]
    elif r-l <= 0:
        # print("err")
        return 0
    else:
        if l+2 >= r:
            #print("err->ret empty")
            return -1
        else:
            # print("update")
            dp[l][r-1] = min(dfs(l, v)+dfs(v, r)
                             for v in range(l+1, r))+sum(A[l:r])
            return dp[l][r-1]


dfs(0, N)
# print(dp)
#print("ans->", dp[0][-1])
print(dp[0][-1])


Fixed submission:
from itertools import accumulate
import sys
# python template for atcoder1
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
            #print("l,r->", l, r)
            tmp = float('inf')
            for m in range(l+1, r):
                tmp = min(tmp, dp[l][m-1]+dp[m][r-1])
            #print("tmp->", tmp)
            #print("acc->", a_acc[r]-a_acc[l])
            dp[l][r-1] = tmp+a_acc[r]-a_acc[l]


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

Buggy python submission (verdict: Time Limit Exceeded):
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

dp = [[float('inf')]*N for _ in range(N)]
for i in range(N):
    dp[i][i] = 0


def dfs(l, r):
    """
    List[l:r]
    """
    #print("l,r->", l, r)
    # print(A[l:r])
    if r-l == 1:
        # print("sole")
        return 0
    if r-l == 2:
        # print("double")
        dp[l][r-1] = A[l]+A[r-1]
        return dp[l][r-1]
    elif r-l <= 0:
        # print("err")
        return 0
    else:
        if l+2 >= r:
            #print("err->ret empty")
            return -1
        else:
            # print("update")
            dp[l][r-1] = min(dfs(l, v)+dfs(v, r)
                             for v in range(l+1, r))+sum(A[l:r])
            return dp[l][r-1]


dfs(0, N)
# print(dp)
#print("ans->", dp[0][-1])
print(dp[0][-1])


Fixed submission:
from itertools import accumulate
import sys
# python template for atcoder1
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
            #print("l,r->", l, r)
            tmp = float('inf')
            for m in range(l+1, r):
                tmp = min(tmp, dp[l][m-1]+dp[m][r-1])
            #print("tmp->", tmp)
            #print("acc->", a_acc[r]-a_acc[l])
            dp[l][r-1] = tmp+a_acc[r]-a_acc[l]


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