Go: package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

//util
var sc = bufio.NewScanner(os.Stdin)

func nextStr() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func printList(list []int) {
	buf := bufio.NewWriter(os.Stdout)
	for _, v := range list {
		buf.Write([]byte(fmt.Sprintf(" %d", v)))
	}
	buf.Write([]byte("\n"))
	buf.Flush()
}

//solve
//単純な場合
func matrixChainMultiplication() {
	//行列が1つだけのとき
	for i := 1; i <= n; i++ {
		m[i][i] = 0
	}
	for l := 2; l <= n; l++ {
		for i := 1; i <= n-l+1; i++ {
			j := i + l - 1
			m[i][j] = 1 << 21
			//kまでで区切る
			for k := i; k <= j-1; k++ {
				m[i][j] = min(m[i][j], m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j])
			}
		}
	}
}

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func min(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}

const MAX = 100

var n int
var p [MAX + 1]int

//m[i][j]: Mi * Mi+1 * ... * Mjを計算するときに必要なスカラー乗算の最小回数
var m [MAX + 1][MAX + 1]int

func main() {
	sc.Split(bufio.ScanWords)
	n = nextInt()
	for i := 1; i <= n; i++ {

		p[i-1] = nextInt() //行数
		p[i] = nextInt()   //列数
	}

	matrixChainMultiplication()
	fmt.Println(m[1][n])
}

Python: n = int(input())
A = [list(map(int, input().split())) for i in range(n)]

ans = [[None for i in range(n)] for j in range(n)]


# for文で動的計画法
def dp1(i, j):
    if ans[i][j] is not None:
        return ans[i][j]
    else:
        if i == j:
            ans[i][j] = 0
        else:
            ret = float('INF')
            for k in range(i, j):
                tmp = dp1(i, k) + A[i][0]*A[k][1]*A[j][1] + dp1(k+1, j)
                ret = min(ret, tmp)
            ans[i][j] = ret
        return ans[i][j]


print(dp1(0, n-1))

Python: INF = float('inf')
mm = [(-1,-1)]
n = int(input())
for _ in range(n):
    mm.append(tuple((map(int,input().split()))))

def scala(a,b,c):
    return mm[a][0] * mm[b][1] * mm[c][1] 

dp = [[INF for _ in range(n+1)] for _ in range(n+1)]
#init
for i in range(1,n):
    dp[i][i+1] = mm[i][0] * mm[i+1][1] * mm[i][1]
    dp[i][i] = 0
dp[-1][-1] = 0
#begin dp
for d in range(2,n):
    for l in range(1,n-d+1):
        r = l + d
        for m in range(l,r):
            dp[l][r] = min(dp[l][m] + dp[m+1][r] + scala(l,r,m), dp[l][r])
print(dp[1][n])
#for i in range(n+1):
#    print(dp[i])
#for d in range(2,n):
#    for l in range(1,n-d+1):
#        r = l + d
#        for m in range(l,r):
#            dp[l][r] = max(dp[l][m] + dp[m+1][r] + scala(l,r,m), dp[l][r])

#print(dp[1][n])
#for i in range(n+1):
#    print(dp[i])

Python: INF = 10**10


def rec(l:int, r:int) -> int:
    if dp[l][r] != INF:
        return dp[l][r]
    elif r - l == 1:
        dp[l][r] = 0
        return 0
    elif r - l == 2:
        dp[l][r] = M[l][0] * M[l][1] * M[l+1][1]
        return dp[l][r]
    else:
        for i in range(l+1, r):
            dp[l][r] = min(dp[l][r], rec(l, i) + rec(i, r) + M[l][0] * M[i-1][1] * M[r-1][1])
    return dp[l][r]


if __name__ == "__main__":
    N = int(input())
    M = [tuple(map(int, input().split())) for _ in range(N)]
    dp = [[INF]*(N+1) for _ in range(N+1)]
    print(rec(0, N))

Python: def s():
 n=int(input())+1
 e=[input().split()for _  in[0]*~-n]
 p=[int(e[0][0])]+list(int(x[1])for x in e)
 m=[[0]*n for _ in[0]*n]
 for i in range(n):
  for r in range(n-i-1):
   c=r+i+1
   for j in range(r+1,c):
    x=m[r][j]+m[j][c]+p[r]*p[j]*p[c]
    if 1>m[r][c]or m[r][c]>x:m[r][c]=x
 print(m[r][c])
if'__main__'==__name__:s()

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

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

def mincost(x,y):
    if dp[x][y]>0:
        return dp[x][y]
    elif x>=y:
        return dp[x][y]
    else:
        res=float('inf')
        for k in range(x,y):
            temp=mincost(x,k)+mincost(k+1,y)+M[x][0]*M[k][1]*M[y][1]
            res=min(res,temp)
        dp[x][y]=res
        return dp[x][y]

print(mincost(0,n-1))

Python: n = int(input())

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

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

p = [M[0][0]]

for i in range(n):
  p.append(M[i][1])

f_inf = float("inf")

m = [[f_inf for i in range(n)] for j in range(n)]

def matrixChainOrder(n):
  for i in range(n):
    m[i][i] = 0
  for l in range(2, n+1):
    for i in range(n-l+1):
      j = i + l - 1
      for k in range(i, j):
        q = m[i][k] + m[k+1][j] + p[i]*p[k+1]*p[j+1]
        if q < m[i][j]:
          m[i][j] = q

matrixChainOrder(n)

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

Python: import sys

p=[0 for i in range (101)]
m=[[0 for i in range(100)]for i in range(100)]

def MatrixChain(n) : 
	for i in range(1,n+1) : m[i][i] = 0;
	for l in range(2,n+1) :
		for i in range(1,n-l+2) : 
			j = i + l - 1
			m[i][j] = float('Infinity')
			for k in range(i,j) :
				q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]
				m[i][j] = m[i][j] if m[i][j] <= q else q

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

MatrixChain(n)
print(m[1][n])

Python: INF = float("inf")
n = int(input())
z = []
m = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    a, b = map(int, input().split())
    z.append(a)
z.append(b)
for l in range(1, n):
    for i in range(1, n - l + 1):
        j = i + l
        m[i][j] = INF
        for k in range(i, j):
            m[i][j] = min(m[i][j], m[i][k] + m[k + 1][j] + z[i - 1] * z[k] * z[j])
print(m[1][n])

Python: import sys

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

lrg = 1000000
DP = [[lrg for i in range(n)] for j in range(n)]


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

if n >= 1:
    for i in range(n-1):
        DP[i][i+1] = m[i][0]*m[i][1]*m[i+1][1]

for d in range(2,n):
    for i in range(n-d):
        for j in range(i+1,i+d):
            DP[i][i+d] = min(DP[i][i+d],DP[i][j]+DP[j+1][i+d]+m[i][0]*m[j][1]*m[i+d][1])

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

Python: n = int(input())

dimensions = []
for i in range(n):
    a, b = map(int, input().split())
    if i == 0:
        dimensions.append(a)
    dimensions.append(b)
inf = float('inf')
dps = [[inf for _ in range(n)] for _ in range(n)]
for i in range(n):
    dps[i][i] = 0
for i in range(n - 1, -1, -1):
    for j in range(i + 1, n):
        for k in range(i, j):
            dps[i][j] = min(dps[i][j],
                            dps[i][k] + dps[k + 1][j] + (dimensions[i] * dimensions[k + 1] * dimensions[j + 1]))
print(dps[0][n - 1])

Python: N = int(input())
M = [[int(x) for x in input().split()] for _ in range(N)]

p = []

for m in M:
    p.append(m[0])

p.append(M[-1][1])

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

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

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

Python: # http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_B&lang=ja
# http://algorithms.blog55.fc2.com/blog-entry-66.html
# https://www.geeksforgeeks.org/python-program-for-matrix-chain-multiplication-dp-8/
import sys

sys.setrecursionlimit(10 ** 6)
n = int(input())
r = []
for i in range(n):
    a, b = map(int, input().split())
    if i == 0:
        r.append(a)
        r.append(b)
    else:
        r.append(b)

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


# dp[i][j] MiMi+1...Mjを計算する最適なコスト
# M[1][2] = M[1][1] + M[2][2] +
def chain_order(i, j):
    if i == j:
        return 0
    if dp[i][j] != float('inf'):
        return dp[i][j]
    for k in range(i, j):
        dp[i][j] = min(dp[i][j], chain_order(i, k) + chain_order(k + 1, j) + r[i - 1] * r[k] * r[j])
    return dp[i][j]


# print(r)
print(chain_order(1, len(r)-1))