Go: package main

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

const (
	initialBufSize = 100000
	maxBufSize     = 1000000
)

var sc *bufio.Scanner

func initScanner(r io.Reader) *bufio.Scanner {
	buf := make([]byte, initialBufSize)

	sc := bufio.NewScanner(r)
	sc.Buffer(buf, maxBufSize)
	sc.Split(bufio.ScanWords) // bufio.ScanLines
	return sc
}

func main() {
	sc = initScanner(os.Stdin)
	fmt.Println(resolve(parseProblem()))
}

type matrixSize struct{ row, col int }

func calcNum(i, j matrixSize) int {
	return i.row * j.col * i.col
}

func parseProblem() (int, []matrixSize) {
	n := scanInt(sc)
	sizes := make([]matrixSize, n)
	for i := 0; i < n; i++ {
		sizes[i] = matrixSize{row: scanInt(sc), col: scanInt(sc)}
	}
	return n, sizes
}

var dp [][]int

func initDP(n int) {
	dp = make([][]int, n+1)
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]int, n+1)
		for j := 0; j < len(dp[i]); j++ {
			dp[i][j] = math.MaxInt64
		}
	}
}

func resolve(n int, sizes []matrixSize) int {
	// TODO 復習
	initDP(n)
	_rec(sizes, 0, n)
	return dp[0][n]
}

func _rec(sizes []matrixSize, l, r int) int {
	if dp[l][r] != math.MaxInt64 {
		return dp[l][r]
	}
	if r-l <= 1 {
		dp[l][r] = 0
		return 0
	}
	num := math.MaxInt64
	for i := l + 1; i < r; i++ {
		v := _rec(sizes, l, i) + _rec(sizes, i, r) + calcNum(matrixSize{sizes[l].row, sizes[i].row}, matrixSize{sizes[i].row, sizes[r-1].col})
		if v < num {
			num = v
		}
	}
	dp[l][r] = num
	return dp[l][r]
}

// snip-scan-funcs
func scanInt(sc *bufio.Scanner) int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return int(i)
}
func scanString(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

Python: import sys


def getmin(i, j, mlist, memo={}):
    if i == j:
        return 0
    elif (i, j) in memo:
        return memo[(i, j)]
    else:
        ret = sys.maxsize
        for k in range(i, j):
            p = mlist[i][0]
            n = mlist[k][1]
            q = mlist[j][1]
            tmp = getmin(i, k, mlist, memo) + \
                getmin(k+1, j, mlist, memo) + p*n*q

            if tmp < ret:
                ret = tmp

        memo[(i, j)] = ret
        return memo[(i, j)]


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

    print(getmin(0, n-1, M))


if __name__ == '__main__':
    main()

Python: N=int(input())

input_=[N]
for n in range(N):
    input_.append(input())
    
P=[]
for n in range(N):
    P.append(int(input_[n+1].split()[0]))
    
P.append(int(input_[n+1].split()[1]))

M=[[0]*(N) for x in range(N)]

for n in range(1,N):
    for i in range(N-n):
        M[i][i+n]=10**100
        for k in range(i,i+n):
            P_0=P[i]
            P_1=P[k+1]
            P_2=P[i+n+1]
            M_=M[i][k]+M[k+1][i+n]+P_0*P_1*P_2
            M[i][i+n]=min(M[i][i+n],M_)
            
print(M[0][-1])

Python: N = int(input())

for i in range(N):
    if i == 0:
        P = list(map(int, input().split()))
        continue
    P.append(int(input().split()[1]))

INF = 2 ** 32 - 1
dp = [[INF] * N for _ in range(N)]

for ij in range(N):
    dp[ij][ij] = 0

for l in range(1, N):
    for i in range(N):
        j = i + l
        if j >= N:
            continue
        for k in range(i, j):
            dp[i][j] = min(dp[i][k] + dp[k+1][j] + P[i] * P[j+1]*P[k+1],
                           dp[i][j])

print(dp[0][-1])

Python: #!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys


def mat_mul_opt(_mat_info):
    rc_info.extend(list(map(int, _mat_info[0])))
    rc_info.extend(list(map(lambda x: int(x[1]), _mat_info[1:])))

    for l in range(2, mat_num + 1):
        for i in range(1, mat_num - l + 2):
            j = i + l - 1
            ans[i][j] = 1e7
            for k in range(i, j):
                ans[i][j] = min(ans[i][j], ans[i][k] + ans[k + 1][j] +
                                rc_info[i - 1] * rc_info[k] * rc_info[j])

    return ans[1][mat_num]


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    mat_num = int(_input[0])
    mat_info = tuple(map(lambda x: x.split(), _input[1:]))

    rc_info = []
    ans = [[0] * (mat_num + 1) for _ in range(mat_num + 1)]
    print(mat_mul_opt(mat_info))

Python: def main():
    """ MAIN """
    DAT = []
    num = int(input())
    for i in range(num):
        x, y = list(map(int,input().split()))
        DAT.append(x)
    DAT.append(y)
    num1 = num + 1
    TBL = [[0] * num1 for i in range(num1)]

    for i in range(0, num1):
        for row in range(num-i):
            col = row + i + 1
            for j in range(row+1,col):
                x = DAT[row] * DAT[j] * DAT[col] + TBL[row][j] + TBL[j][col]
                if TBL[row][col] < 1 or TBL[row][col] > x:
                    TBL[row][col] = x

    print("{}".format(TBL[row][col]))

if __name__ == '__main__':
    main()

Python: #!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys


def mat_mul_opt(_mat_info):
    rc_info = list(map(int, _mat_info[0]))
    rc_info.extend(list(map(lambda x: int(x[1]), _mat_info[1:])))

    for l in range(2, mat_num + 1):
        for i in range(1, mat_num - l + 2):
            j = i + l - 1
            ans[i][j] = 1e7
            for k in range(i, j):
                ans[i][j] = min(ans[i][j], ans[i][k] + ans[k + 1][j] +
                                rc_info[i - 1] * rc_info[k] * rc_info[j])

    return ans[1][mat_num]


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    mat_num = int(_input[0])
    mat_info = tuple(map(lambda x: x.split(), _input[1:]))
    # assert len(mat_info) == mat_num

    ans = [[0] * (mat_num + 1) for _ in range(mat_num + 1)]
    print(mat_mul_opt(mat_info))

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: # coding=utf-8


def calc_cost():
    global M
    for diff in range(0, n):
        for i in range(1, n-diff+1):
            j = i + diff
            if diff == 0:
                M[i][j] = 0
            elif diff == 1:
                M[i][j] = p[i-1] * p[i] * p[j]
            else:
                M[i][j] = calc_min(i, j)
            ### debugger ###
            #for row in M:
            #    print(*row)
    return M[1][n]

def calc_min(i, j):
    global M, p
    min_cost = float("inf")
    for k in range(i, j):
        cost = M[i][k] + M[k+1][j] + (p[i-1] * p[k] * p[j])
        #print("i, j, k, cost:", i, j, k, cost)
        if cost < min_cost:
            min_cost = cost
    return min_cost

n = int(input())
M = [["-" for _ in range(n+1)] for _ in range(n+1)]
r_list = []
c_list = []
p = []
for _ in range(n):
    r, c = map(int, input().split())
    r_list.append(r)
    c_list.append(c)

p.append(r_list[0])
for c in c_list:
    p.append(c)

total_cost = calc_cost()
print(total_cost)

Python: import math

n = int(input())
dp = [[0 for j in range(n+1)] for i in range(n+1)]
p = []

def init(p):
    global dp
    for i in range(1, n):
        dp[i][i+1] = p[i-1]*p[i]*p[i+1]

def solve(r, c):
    global dp
    smallest = math.inf
    for i in range(r, c):
        temp = p[r-1]*p[i]*p[c] + dp[r][i] + dp[i+1][c]
        if temp < smallest:
            smallest = temp
    return smallest

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

init(p)
for j in range(3, n+1):
    for i in range(j-2, 0, -1):
        dp[i][j] = solve(i, j)
print(str(dp[1][n]))