Go: package main

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

type Matrix struct {
	r int // num of row
	c int // num of column
}

type Range struct {
	start int // index, inclusive
	end   int // index, inclusive
}

func calcMultiplication(x, y Matrix) (Matrix, int) {
	if x.c != y.r {
		panic("cannnot calculate")
	}
	return Matrix{x.r, y.c}, x.r * y.c * x.c
}

func calcMinMatrixChainMultiplication(matrices []Matrix, r Range, memo map[Range]int) (Matrix, int) {
	if v, ok := memo[r]; ok {
		return Matrix{matrices[0].r, matrices[len(matrices)-1].c}, v
	}
	if len(matrices) == 0 {
		panic("must not be empty")
	} else if len(matrices) == 1 {
		return matrices[0], 0
	} else if len(matrices) == 2 {
		return calcMultiplication(matrices[0], matrices[1])
	}

	var minCount int = math.MaxInt32

	for i := 0; i < len(matrices)-1; i++ {
		formerMatrices := matrices[:i+1]
		latterMatrices := matrices[i+1:]
		matF, countF := calcMinMatrixChainMultiplication(formerMatrices, Range{0, i}, memo)
		matL, countL := calcMinMatrixChainMultiplication(latterMatrices, Range{i + 1, len(matrices) - 1}, memo)
		_, countFL := calcMultiplication(matF, matL)
		count := countF + countL + countFL
		if count < minCount {
			minCount = count
		}
	}
	return Matrix{matrices[0].r, matrices[len(matrices)-1].c}, minCount
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	n, _ := nextInt(sc)
	matrices := make([]Matrix, n)
	for i := 0; i < n; i++ {
		r, _ := nextInt(sc)
		c, _ := nextInt(sc)
		matrices[i] = Matrix{r, c}
	}
	memo := make(map[Range]int)
	_, resultCount := calcMinMatrixChainMultiplication(matrices, Range{0, len(matrices) - 1}, memo)
	fmt.Println(resultCount)
}

func nextInt(sc *bufio.Scanner) (int, error) {
	sc.Scan()
	return strconv.Atoi(sc.Text())
}

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

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

for l in range(2, n + 1):
    for i in range(n - l + 1):
        j = i + l - 1
        m[i][j] = float('inf')
        for k in range(i, j):
            m[i][j] = min(m[i][j], m[i][k] + m[k + 1][j] + p[i][0] * p[k][1] * p[j][1])

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

Python: import sys
def s():
 n=int(input())+1
 e=list(map(lambda x:x.split(),sys.stdin))
 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: import sys

sys.setrecursionlimit(10**7)

inf = float('inf')

def solve():
    n = int(sys.stdin.readline())

    r = [0] * n
    c = [0] * n

    for i in range(n):
        ri, ci = map(int, sys.stdin.readline().split())
        r[i] = ri
        c[i] = ci

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

    ans = mcm(memo, n, r, c, 0, n)

    # print(memo)

    print(ans)

def mcm(memo, n, r, c, left, right):
    if memo[left][right] != -1:
        return memo[left][right]
    elif right - left == 1:
        memo[left][right] = 0
        return 0
    else:
        res = inf

        for i in range(left + 1, right):
            res = min(res, mcm(memo, n, r, c, left, i) + mcm(memo, n, r, c, i, right) + r[left]*r[i]*c[right-1])

        memo[left][right] = res
        return res

def compute_lcs(x, y):
    n = len(x)
    m = len(y)

    x = '#' + x
    y = '#' + y

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

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if x[i] == y[j]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[n][m]

if __name__ == '__main__':
    solve()

Python: import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    dp = [[0] * (N + 1) for _ in range(N + 1)]
    p = [0] * (N + 1)
    for i in range(N):
        p[i], p[i + 1] = il()

    for l in range(2, N + 1):
        for i in range(1, N - l + 2):
            j = i + l - 1
            dp[i][j] = MAX
            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()