Go: package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)
	a := make([]int, n+1)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i])
		fmt.Scan(&a[i+1])
	}

	m := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		m[i] = make([]int, n+1)
	}

	for d := 2; d <= n; d++ {
		for s := 0; s+d <= n; s++ {
			min := 1 << 30
			for j := s+1; j < s+d; j++ {
				val := m[s][j] + m[j][s+d] + a[s]*a[j]*a[s+d]
				if val < min {
					min = val
				}
			}
			m[s][s+d] = min
		}
	}
	fmt.Println(m[0][n])
}

Python: #!/usr/bin/env python3
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)




n=int(input())
M=[0]*(n+1)
for i in range(n):
    M[i],M[i+1]=map(int,input().split())
dp=[[float('inf')]*n for i in range(n)]
for i in range(n):
    dp[i][i]=0
for k in range(1,n):
    for i in range(n-k):
        j=i+k
        for l in range(i,j):
            dp[i][j]=min(dp[i][j],dp[i][l]+dp[l+1][j]+M[i]*M[l+1]*M[j+1])
print(dp[0][n-1])
# print(dp)

Python: def matrix_chain_multiplication(n, list):
    matrix = [[0 for i in range(n)] for j in range(n)]

    for i in range(n-1):
        for j in range(n-i-1):
            k = j+i+1
            matrix[j][k] = float('inf')
            for r in range(j, k):
                matrix[j][k] = min(matrix[j][k],
                    matrix[j][r] + matrix[r+1][k]
                    + list[j]*list[r+1]*list[k+1])

    return matrix[0][n-1]

if __name__ == '__main__':
    n = int(input())

    list = list(map(int, input().split()))
    for i in range(n-1):
        list.append(int(input().split()[1]))

    print(matrix_chain_multiplication(n, list))

Python: import sys
input = sys.stdin.readline
INF = 1001001001001001
def main():
    n = int(input())
    p = [0] * (n+1)
    for i in range(n):
        p[i], p[i+1] = map(int, input().split())
    dp = [[INF]*(n+1) for _ in range(n+1)]
    for i in range(n+1):
        dp[i][i] = 0
    for l in range(2, n+1):
        for i in range(n-l+2):
            j = i + l - 1
            for k in range(i, j):
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j])
    print(dp[1][n])
if __name__ == '__main__': main()

Python: n = int(input())
p = list(range(n+2))

for i in range(1,n+1):
    p[i], p[n+1] = map(int, input().split())

# table[i][j] : M_i??????M_j??????????????????????°?????????°
table = [[0] * (n+1) for i in range(n+1)]

# ??£????????£???2????????????????????????
for i in range(1,n):  # 1<=i,i+1<=n
    table[i][i+1] = p[i]*p[i+1]*p[i+2]


for k in range(3, n+1):    # ?????????k???????????????????????????3<=k<=n
    for i in range(1,n+2-k): # M_i?????????1<=i<=n-k+1
        j = i + k - 1      # M_j?????§???k??????

        table[i][j] = float('inf')

        for x in range(i, j): # M_i~M_x??¨M_(x+1)~M_j??§????????????(i<=x,x+1<=j<=n)
            print(i, x, j)
            cost = table[i][x] + table[x+1][j] + p[i]*p[x+1]*p[j+1]
            table[i][j] = min(table[i][j], cost)
            

print(table[1][n])

Python: """
n = input().split()

n = input()
nele = int(n[0])
list = range(1,nele+1)

nrow = {}
ncol = {}
for i in list:
	nrow[i] = int(n[i*2-1])
	ncol[i] = int(n[i*2])
"""

n = input()
nele = int(n[0])
list = range(1,nele+1)
nrow = {}
ncol = {}
for i in list:
	n = input().split()
	nrow[i] = int(n[0])
	ncol[i] = int(n[1])


#print(nrow, ncol)


min = -1
cur = -1
route = []
done = []

for i in list:
	route.append(0)

#print(route)

depth = -1
min = -1
def tansaku(prev, row_prev):
	
	global depth
	depth += 1
	
	global nrow
	global ncol
	global min
	global route
	
	done = route[:]
	
	for i in list:
#		print(depth, i, route, done)
		
		if i in done:
			continue
		
		next = i
		done.append(next)
		
		if depth == 0:
			route[depth] = next
			tmp = 0
			row_next = nrow[next]
			min = tansaku(tmp, row_next)
			continue
#		print(route, route[depth-1], next, nrow[route[depth-1]], ncol[next], prev)
#		tmp = prev + nrow[route[depth-1]] * ncol[next]
#		print(prev, row_prev, ncol[next])
		tmp = prev + row_prev * ncol[next]
		row_next = ncol[next]
#		print(depth, tmp)
		
		if tmp > min and min != -1:
#			print("aaa")
			continue
		else:
			route[depth] = next
			if depth >= nele-1:
#				print("bbb")
				min = tmp
			else:
#				print("ccc")
				min = tansaku(tmp, row_next)
	
	depth -= 1
	route[depth] = 0
#	print("min:", min)
	return min

min = tansaku(0, 0)

print(min)

Python: INF = 1e9

def MatrixChainMulti(n, p):
    dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
    
    for i in range(n+1):
        dp[i][i] = 0
        
    for l in range(1, n): # 1<= l <= n-1
        for i in range(0, n-l+1): #0<= i <= n-l
            j = i + l
            dp[i][j] = INF
            for k in range(i, j): # i<= k <= j-1
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j])
    
    return dp[1][n]

N = int(input())
p = []
a, b = list(map(int, input().split()))
p.append(a)
p.append(b)

for _ in range(N-1):
    c, d = list(map(int, input().split()))
    p.append(d)
    
print(MatrixChainMulti(N, p))

Python: def matrixChainMultiplication(M):
    # P ??????
    n = len(M)
    P = [M[0][0]]
    P += [M[i][1] for i in range(n)]
    # ?¨???¶?????? m ??????
    m = [[[] for _ in range(n + 1)] for _ in range(n + 1)]
    for i in range(n + 1):
            m[i][i] = 0

    # l???????±???¨?????????????????°
    for l in range(2, n + 1):
        for i in range(1, n - l + 2):
            j = i + l - 1
            m[i][j] = 9999999999999999
            for k in range(i, j):
                m[i][j] = min(m[i][j], m[i][k] + m[k + 1][j] + P[i -1] * P[k] * P[j])
    return m[1][n]


if __name__ == '__main__':
    n = int(input())
    M = [list(map(int, input().split())) for _ in range(n)]
    print(matrixChainMultiplication(M))

Python: n = int(input())
INFTY = 10**8

p = [0]*(n+1)
for i in range(n):
    roww = input().split()
    p[i] = int(roww[0])
    p[i+1] = int(roww[1])

M = [[0]*n for i in range(n)]

def matricChainMultiplication(n, p, M):
#     2つの行列積のmin, 次は3という風に増やしていく
    for l in range(2, n+1):
        for i in range(0, n - l + 1):
            j = i + l - 1 #積を見る最大のIndex
            M[i][j] = INFTY
            for k in range(i, j):
                M[i][j] = min(M[i][j],
                              M[i][k] + M[k+1][j] +
                              p[i] * p[k+1] * p[j+1] )
#                 print(l, i, j, k, M[i][j])
    return M[0][n-1]

print(matricChainMultiplication(n, p, M))

Python: """
n = input().split()

n = input()
nele = int(n[0])
list = range(1,nele+1)

nrow = {}
ncol = {}
for i in list:
	nrow[i] = int(n[i*2-1])
	ncol[i] = int(n[i*2])
"""

n = input()
nele = int(n[0])
list = range(1,nele+1)
nrow = {}
ncol = {}
for i in list:
	n = input().split()
	nrow[i] = int(n[0])
	ncol[i] = int(n[1])


#print(nrow, ncol)


min = -1
cur = -1
route = []
done = []

for i in list:
	route.append(0)

#print(route)

depth = -1
min = -1
def tansaku(prev, row_prev):
	
	global depth
	depth += 1
	
	global nrow
	global ncol
	global min
	global route
	
	done = route[:]
	
	for i in list:
#		print(depth, i, route, done)
		
		if i in done:
			continue
		
		next = i
		done.append(next)
		
		if depth == 0:
			route[depth] = next
			tmp = 0
			row_next = nrow[next]
			min = tansaku(tmp, row_next)
			continue
#		print(route, route[depth-1], next, nrow[route[depth-1]], ncol[next], prev)
#		tmp = prev + nrow[route[depth-1]] * ncol[next]
#		print(prev, row_prev, ncol[next])
		tmp = prev + row_prev * ncol[next]
		row_next = ncol[next]
#		print(depth, tmp)
		
		if tmp > min and min != -1:
#			print("aaa")
			continue
		else:
			route[depth] = next
			if depth >= nele-1:
#				print("bbb")
				min = tmp
			else:
#				print("ccc")
				min = tansaku(tmp, row_next)
	
	depth -= 1
	route[depth] = 0
#	print("min:", min)
	return min

min = tansaku(0, 0)

print(min)